循环处理第i个和第i+1个元素的Clojure惯用语

Question

我一直在思考如何实现一个算法来计算多边形关于一个点的绕数。目前的实现方式如下：（注意更新代码以使其正常工作）

(defn winding-num
  "Return winding number of polygon
  see Alciatore "
  [poly point]
        ; translate poly such that point is at origin
  (let [translated-poly (map #(vec-f - % point) poly)]
    ; w is wind-num
    (loop [vertices translated-poly w 0]
      (cond
        (= (count vertices) 1)
        w

        :else
        (let [x1 (first (first vertices))
              x2 (first (second vertices))
              y1 (second (first vertices))
              y2 (second (second vertices))]
          (cond 
            (and (< (* y1 y2) 0)
                 (> (+ x1 (/ (* y1 (- x2 x1))
                         (- y1 y2)))
                    0))
            (if (< y1 0)
                (recur (rest vertices) (inc w))
                (recur (rest vertices) (dec w)))

            (and (zero? y1)
                 (> x1 0))
            (if (> y2 0)
                (recur (rest vertices) (+ w 0.5))
                (recur (rest vertices) (- w 0.5)))

            (and (zero? y2)
                 (> x2 0))
            (if (< y1 0)
                 (recur (rest vertices) (+ w 0.5))
                 (recur (rest vertices) (- w 0.5)))

            :else
            (recur (rest vertices) w)))))))

我的问题是：

• 人们说在可能的情况下使用比显式递归更高级别的循环结构更好，例如map，for，reduce等。
• rest函数将向量转换为列表

我可以想到一种使用for和索引的实现方式，但我也听说最好不要使用索引。

有没有处理需要访问连续值的向量算法的惯用方法？

- zenna

---

vec-f只是我写的一个函数，旨在使向量操作更加方便，在此情况下它将一个向量从另一个向量中相减。 - zenna

如Rob所说，你可能正在寻找分区。但是，如果你想要速度的话，使用loop/recur应该是最快的。你可能还想考虑在let中使用解构来消除一些重复，就像这样： (let [[[x1 y1] [x2 y2]] vertices coll (rest vertices)] ... - bmaddy

Answer 1

一般来说，如果您想访问序列的连续值，每次两个，您可以使用partition函数。Partition函数允许您指定组大小和步长：

user> (partition 2 1 (range 10))
((0 1) (1 2) (2 3) (3 4) (4 5) (5 6) (6 7) (7 8) (8 9))

- Rob Lachlan

Answer 2

这真的取决于你算法的形状。一般来说，高级结构比显式递归更易理解，但有时问题的形状会使这一点不太清楚。

其他需要注意的事项：

rest 返回一个序列，而不是一个列表。这在这里并不重要。

你应该使用解构。例如：

    (let [x1 (first (first vertices))
          x2 (first (second vertices))
          y1 (second (first vertices))
          y2 (second (second vertices))

这可以被替换为：

(let [[x1 y1] [x2 y2]] vertices] ... )

然而，使用 reduce 实现这个算法并不是非常困难：

(defn inc-dec 
  "Convenience function for incrementing and decrementing"
  ([condition i] (if condition (inc i) (dec i)))
  ([condition i amount] (if condition (+ i amount) (- i amount))))

(defn winding-num
  [poly point]
  (let [translated-poly (map #(map - % point) poly)
        winding-reducer
          (fn winding-reducer [w [[x1 y1] [x2 y2]]]
            (cond 
              (and (< (* y1 y2) 0)
                      ; r
                   (> (+ x1 (/ (* y1 (- x2 x1))
                           (- y1 y2)))
                      0))
               (inc-dec (< y1 0) w)

              (and (zero? y1) (> x1 0))
               (inc-dec (> y2 0) w 0.5)

              (and (zero? y2) (> x2 0))
               (inc-dec (< y1 0) w 0.5)

              :else w))
        ]
    (reduce winding-reducer 0 (partition 2 1 translated-poly))))

- Francis Avila

---

感谢您提供有关解构的提示，我知道这个概念，但还没有学习过其语法。如何处理“rest”？我现在将代码更新为可工作和完整的版本，一个简单的测试用例是（winding-num [[0.0 0.0] [1.0 0.0] [1.0 1.0] [0.0 1.0]] [0.5 0.5]）。这是一个带有多边形中心的盒子，旋转数应该为0。如果将点移动到外面，即第二个参数为[2.0 2.0]，则应该计算为1。 - zenna

我认为你把那些结果搞反了？ - Francis Avila

这篇文章是关于解构的很好的介绍：http://blog.jayfields.com/2010/07/clojure-destructuring.html - bmaddy

Answer 3

以下代码使用(map func seq (rest seq))来处理算法使用的点对。它还修复了原始实现中的两个问题：

它可以处理多边形是否通过将第一个点重复为最后一个点来指定，即对于两种情况都给出相同的结果。

[[1 1][-1 1][-1 -1][1 -1]] and 

[[1 1][-1 1][-1 -1][1 -1][1 1]] 

它还适用于在正x轴上具有连续点的多边形，而原始代码（和参考伪代码）将从沿着x轴的每条线段中减去1/2。

(defn translate [vec point]
   (map (fn [p] (map - p point)) vec))

(defn sign [x]
  (cond (or (not (number? x)) (zero? x)) 0
        (pos? x) 1
        :else -1))

(defn winding-number [polygon point]
  (let [polygon (translate (conj polygon (first polygon)) point)]
     (reduce +
          (map (fn [[x1 y1][x2 y2]]
                   (cond (and (neg? (* y1 y2))
                              (pos? (- x2 (* y2 (/ (- x2 x1) (- y2 y1))))))
                           (sign y2)
                         (and (zero? y1) (pos? x1))
                           (sign y2)
                         (and (zero? y2) (pos? x2))
                           (sign y1)
                         :else 0))
                polygon (rest polygon)))))

- Terje D.