Jarvis March in Clojure

Posted by Uncle Bob on 08/11/2009

OK, all you Clojure gurus, I need your help. I need to speed this algorithm up.

Just for fun I thought I’d write the Jarvis March algorithm in Clojure. This algorithm is for finding the convex hull of a collection of points. The basic idea is really simple. Imagine that all the points in the collection are represented by nails in a board. Find the left-most nail and tie a string to it. Then wind the string around the nails. The string will only touch nails that are part of the convex hull.

The details are not really that much more difficult. You start at the left-most point and calculate the angle from vertical required to touch every other point. The point with the minimum angle is the next point. You keep going around looking finding points with the minimum angle that is greater than the previous angle. When you get back to the starting point you are done.

Calculating angles can be time consuming, so I use a psuedo-angle algorithm. It doesn’t calculate the actual angle, rather it is a function that increases with the true angle, and goes from [0, 4).

The code is pretty simple.

(ns convexHull.convex-hull   (:use clojure.contrib.math))  (defn quadrant-one-pseudo-angle [dx dy]   (/ dx (+ dy dx)))  (defn pseudo-angle [[dx dy]]   (cond     (and (= dx 0) (= dy 0))     0      (and (>= dx 0) (> dy 0))     (quadrant-one-pseudo-angle dx dy)      (and (> dx 0) (<= dy 0))     (+ 1 (quadrant-one-pseudo-angle (abs dy) dx))      (and (<= dx 0) (< dy 0))     (+ 2 (quadrant-one-pseudo-angle (abs dx) (abs dy)))      (and (< dx 0) (>= dy 0))     (+ 3 (quadrant-one-pseudo-angle dy (abs dx)))      :else nil))  (defn point-min [[x1 y1 :as p1] [x2 y2 :as p2]]   (cond     (< x1 x2)     p1      (= x1 x2)     (if (< y1 y2) p1 p2)      :else     p2))  (defn find-min-point [points]   (reduce point-min points))  (defn delta-point [[x1 y1] [x2 y2]]   [(- x1 x2) (- y1 y2)])  (defn angle-and-point [point base]   [(pseudo-angle (delta-point point base)) point])  (defn min-angle-and-point [ap1 ap2]   (if (< (first ap1) (first ap2)) ap1 ap2))  (defn find-point-with-least-angle-from [base angle points]   (reduce min-angle-and-point     (remove       #(< (first %) angle)       (map #(angle-and-point % base)         (remove           (fn [p] (= base p))           points)))))  (defn hull [points]   (println "Start")   (let [starting-point (find-min-point points)]     (println starting-point)     (loop [hull-list [starting-point] angle 0 last-point starting-point]       (let [[angle next-point] (find-point-with-least-angle-from last-point angle points)]         (if (= next-point (first hull-list))           hull-list           (recur (conj hull-list next-point) angle next-point))))))

I execute it with this:

(ns convexHull.time-hull   (:use convexHull.convex-hull))  (def r (java.util.Random.)) (defn rands [] (repeatedly #(.nextGaussian r))) (defn points [] (take 400000 (partition 2 (rands)))) (let [hull-points (time (hull (points)))]   (printf "Points: %d\n" (count hull-points))   (doseq [x hull-points] (println x)))

This takes way too long to run. The equivalent java program will do a million points in half a second. This one is taking 25 seconds to do a half-million points. It won’t even do a million points. It slows way way down and then runs out of memory. (There must be some kind of disk caching going on or something.)

Anyway, I’d be interested in seeing how a real Clojure programmer would speed this program up.

Comments

Leave a response