The simplest of the algorithms, the Jarvis March was also one of the first output-sensitive computational geometry algorithms. In a nutshell, you first find a point that you know to be on the convex hull, and then you find the next point by looking at all the rest of the points and determining which one has a segment that has the property that all the rest of the points are on one side of it. You repeatedly find the next point using this procedure until you get back to the first point. There is basically no way to implement this algorithm that does not have a running time of \(O(hn)\), where \(h\) is the number of points on the convex hull and \(n\) is the number of input points.

The one implementation detail of the Jarvis March that is interesting is that whenever you see the concept of "finding the next thing" given some previous information, the Clojure implementation should almost always be lazy. It turns out that implementing Jarvis March lazily will help in implementing Chan's Algorithm, so keep that in mind.

Graham's Scan is one of the algorithms I remember most vividly from the undergraduate computational geometry course that I took. The professor, Godfried Toussaint, always referred to it as the "three coins" algorithm, so I have kept up that tradition in some of my function names in my implementation.

The algorithm first makes a polygon of the input points by sorting them by angle about the bottom-most point. Then it goes around the polygon with a stack, pushing and popping points as it goes. If that sounds familiar, it should – it's the same idea as what I was talking about when I brought up the idea of parsing polygons a week and a half ago.

Thus, I used the same polygon-parsing monad in my implementation as when I computed the visibility polygons last week. It still works just as well.

Since the points must be sorted, Graham's Scan takes \(\Theta(n \log n)\). Sorting can be reduced to computing convex hulls, so computing convex hulls has a \(\Omega(n \log n)\) lower bound, meaning that this algorithm is optimal.

But Chan's algorithm is better. Weird huh?

I must confess that I had always been a little intimidated by Chan's Algorithm. It was invented by Timothy Chan, who has a well-earned reputation for being a genius, so I thought it would be really complicated. It's not. There is a decent description of it on Wikipedia, so I won't go into the details. The gist is that you combine the two previous algorithms that I discussed. The Jarvis March needs to be modified so that the points can be input as a list of smaller convex hulls, and the next point on the convex hull is found by doing a binary search on the smaller convex hulls. But that is really the hardest part about the algorithm. I have put the whole thing below, because I think it's pretty beautiful.

(defn chans-algorithm
  "Finds the convex hull of a set of points by
   the algorithm known as 'Chan's Algorithm'."
  [pts]
  (let [bottom-pt (apply min-key :y pts)]
   (loop [m 3] ; start out with triangles
     (let [partitioned-pts (partition m m [] pts)
           c-hs (map grahams-scan partitioned-pts)
           potential-ch (take m (apply jarvis-march pts c-hs))]
       (if (= bottom-pt (last potential-ch)) ; assumes jarvis-march returns bottom-pt last
         potential-ch
         (recur (min (* m m) (count pts))))))))

The great thing about Chan's Algorithm is that it is also output-sensitive. But instead of being \(O(nh)\) (which is \(O(n^2)\) in the worst case), it is \(O(n \log h)\), which is at least as good as Graham's Scan, but often better. It is also quite simple to implement, given decent implementations of Jarvis March and Graham's Scan.