CODEWITHSUNDEEP
recursionfor-loopclojurelisp
zenna
zenna

Reputation: 9206

Idiomatic clojure for ith and i+1th element looping

I have been trying to think how to implement an algorithm to compute the winding number of a polygon with respect to a point. Currently the implementation is as follows: (note updated so 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 are

I could think of an implementation using for and indices, but I also hear it is preferable to not use indices.

Is there an idiomatic way for dealing with vector algorithms which in each iteration need access to consecutive values?

Upvotes: 4

Views: 265

Answers (3)

Terje D.
Terje D.

Reputation: 6315

The following code is using (map func seq (rest seq)) to handle the pair of points used by the algorithm. It also fixes two problems with the original implementation:

It works whether or not the polygon is specified by 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 successive points on the positive x-axis, whereas the original (and the refered pseudo code) will substract 1/2for 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)))))

Upvotes: 0

Francis Avila
Francis Avila

Reputation: 31641

It really depends on the shape of your algorithm. Generally speaking higher-level constructs are more understandable than explicit recursion, but sometimes the shape of the problem makes this less clear.

Other things to note:

rest returns a sequence, not a list. This shouldn't matter here.

You should make use of destructuring. For example:

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

Upvotes: 1

Rob Lachlan
Rob Lachlan

Reputation: 14479

In general if you want to access consecutive values of a sequence, two at a time, you can use the partition function. Partition allows you to specify a group size as well as a 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))

Upvotes: 4

Related Questions