第i個和第i + 1個元素循環的習慣clojure

Question

我一直在想如何實現一個algorithm來計算相對於一個點的多邊形的圈數。目前實現如下：（注意更新，以便代碼工作）

(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等
• 其餘的功能載體轉換成列表

我能想到用for和指標實現的，但我也聽到它最好不使用索引。

是否有一種處理矢量算法的慣用方式，在每次迭代中需要訪問連續值？

Answer 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)))) 

Answer 2

一般來說，如果你想訪問一個序列的連續值，一次兩個，您可以使用分區功能。分區允許指定的一組尺寸，以及一個步長大小：

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

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)))))