# 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

# Right and Left Turns

In my previous post on line segment intersection I introduced the two dimensional cross product as $v1 \times v2 = {v1}_x \cdot {v2}_y - {v2}_x \cdot {v1}_y.$ The cross product can also be used to determine if a set of three points $p_1, p_2, \textrm{ and } p_3$ make a right turn.

First note that if $v_1 \times v_2 > 0$ then the angle between $v_1$ and $v_2$ is strictly less than $\pi.$ For example the two vectors $(1, 0) \times (0, 1) = 1 \cdot 1 - 0 = 1 > 0.$ Similarly if $v_1 \times v_2 < 0$ then the angle between them is strictly greater than $\pi.$ In the below image I've shown an example where the three points $p_1, p_2, \textrm{ and } p_3$ make a right turn.

To mathematically determine if the points make a right turn we let $v_1 = p_1 - p_2 \textrm{ and } v_2 = p_3 - p_2.$ Then taking the cross product of $v_1 \textrm{ and } v_2,$ we have $v_1 \times v_2 > 0$ which implies that the angle between them is less than $\pi$ that is they make a right turn.

This method for determining whether the points make a right or left turn is very useful for determining the convex hull of a set of points.

I’ve posted an example webpage, here, where using javascript the lines change color depending on whether the turn is to the right or the left. Please note that the page uses the html5 canvas element so it will not work in internet explorer 7, or 6.