Convex Hulls

The algorithm I’m going to showcase is taken from the book “Computational Geometry algorithms and applications” by Berg, Cheong, Kreveld, and Overmars. They give an excellent analysis of the algorithm in the book so I’ll only go over the highlights and show my implementation in Javascript using the html5 canvas.

The problem statement is given a set of points, S = \{p_1, p_2, \ldots, p_n\} in R^2 compute the convex hull of S. The input of the algorithm is the set, S, of points and the output of the algorithm is the set of points that are the vertices of the convex hull of S.

Our algorithm will use a standard design technique to generate what’s called an incremental algorithm. That is we compute the solution for the first p_1, \ldots, p_i points then add the point p_{i+1} and compute the new solution using the previous solution.

Algorithm ConvexHull(P) (the pseudocode is borrowed from “Computational Geometry algorithms and applications”)
Input. A set P of points in the plane
Output. A list containing the vertices of \mathcal{CH}(P) in clockwise order.
1. Sort the points by x-coordinate, resulting in a sequence p_1,\ldots, p_n.
2. Put the points p_1 and p_2 in a list \mathcal{L}_\textrm{upper}, with p_1 as the first point.
3. for i \leftarrow 3 to n
4.        do Append p_i to \mathcal{L}_\textrm{upper}.
5.                        while \mathcal{L}_\textrm{upper} contains more than two points and the last three points in \mathcal{L}_\textrm{upper} do not make a right turn
6.                           do Delete the middle of the last three points from \mathcal{L}_\textrm{upper}.
7. Put the points p_n and p_{n-1} in a list \mathcal{L}_\textrm{lower}, with p_n as the first point.
8. for i \leftarrow n -2 downto 1
9.           do Append p_i to \mathcal{L}_\textrm{lower}.
10.                     while \mathcal{L}_\textrm{lower} contains more than 2 points and the last three points in \mathcal{L}_\textrm{lower} do not make a right turn
11.                     do Delete the middle of the last three points from \mathcal{L}_\textrm{lower}.
12. Remove the first and last point from \mathcal{L}_\textrm{lower}. to ovoid duplication of the points where the upper and lower hull meet.
13. Append \mathcal{L}_\textrm{lower} to \mathcal{L}_\textrm{upper}, and call the resulting list \mathcal{L}.
14. return \mathcal{L}.

You can view an implementation using Javascript and the html5 canvas element, here. To add a new point simply click the left mouse button and it’ll add a point where the mouse is.

Advertisements

One thought on “Convex Hulls

  1. Nice! Might be a cool addition if points part of the convex hull were colored differently to see degenerate cases being handled correctly.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s