Idiomatic clojure for the i-th and i + 1st element cycles

Question

I tried to think about how to implement an algorithm to calculate the number of polygon windings relative to a point. Currently, the implementation is as follows: (note, updated, so the code works)

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

My problems with this:

• People say it is preferable to use loop constructors that work at a higher level than explicit recursion; e.g. map , for , reduce , etc.
• The rest function converts a vector to a list

I might think of an implementation using for and indexes, but I also heard that it is preferable not to use indexes.

Is there an idiomatic way to handle vector algorithms that need to access sequential values ​​at each iteration?

Answer 1

In general, if you want to access the sequential values ​​of a sequence, two at a time, you can use the split function. The section allows you to specify the size of the group, as well as the step size:

 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 2

It depends on the form of your algorithm. In general, higher-level constructs are more understandable than explicit recursion, but sometimes the form of the problem makes this less clear.

Other notes:

rest returns a sequence, not a list. It doesn’t matter here.

You must use destructuring. For instance:

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

This can be replaced by:

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

However, this is not a very complicated algorithm to implement with 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 3

The following code uses (map func seq (rest seq)) to process a pair of points used by the algorithm. It also fixes two problems with the initial implementation:

It works regardless of whether the polygon is specified, repeating the first point as the last, i.e. giving the same result for both

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

It also works for polygons that have consecutive points on the positive x-axis, while the original (and the indicated pseudo-code) will subtract 1/2 for each line segment along the x-axis.

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