4

我一直在尝试思考如何实现一种算法来计算多边形相对于一个点的缠绕数。目前实现如下：（注意更新所以代码有效）

(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和索引的实现，但我也听说最好不要使用索引。

是否有一种惯用的方法来处理在每次迭代中都需要访问连续值的向量算法？

4

3 回答 3

4

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

user> (partition 2 1 (range 10))
((0 1) (1 2) (2 3) (3 4) (4 5) (5 6) (6 7) (7 8) (8 9))
于 2013-04-30T04:04:19.960 回答
1

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

其他需要注意的事项：

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))))
于 2013-04-30T03:15:09.327 回答
0

以下代码(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 轴上具有连续点的多边形，而原始（和引用的伪代码）将减去1/2沿 x 轴的每个线段。

(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)))))
于 2013-04-30T18:41:15.007 回答