Convex hull algorithms

Planar case. Consider the general case when the input to the algorithm is a finite unordered set of points on a Cartesian plane. An important special case is: points are given in the order of traversal of a simple polygon's boundary.

If all points are not on the same line, then their convex hull is a convex polygon whose vertices are some of the points in the input set. Its most common representation is the list of its vertices ordered along its boundary clockwise or counterclockwise. In some applications it is convenient to represent a convex polygon as an intersection of a set of half-planes, as discussed previously.

For an arbitrary set of $n$ points in two and three dimensions, we can compute the convex hull using the Graham Scan, Gift-wrapping and divide-and-conquer algorithms. Note that the convex hull of an arbitrary set of points in two dimensions is a convex polygon.

The Graham scan Algorithm:

1. Sorting the input set of points with respect to an interior point, say $O$, which is centroid of the first three nonlinear points. (The centroid for $(x_1, y_1), (x_2, y_3), (x_3, y_3)$ is $((x_1+x_2+x_3)/3, (y_1+y_2+y_3)/3)$, and sorting of every point $(x_i, y_i)$ is with respect to the angle from centroid $O$.)

2. Connect these points into a star-shaped polygon $P$ centered at $O$ (see figure ).

3. Performing linear scan of the sorted points to compute the convex hull of polygon.

Figure: Graham scan algorithm geometry.

The algorithm takes $O(n\log n)$ time as first step is dominating step, which requires the sorting of all the points. The figure  shows that points $(x_1, y_1), \dots, (x_n, y_n)$, are sorted in the increasing order of the angle, with centroid centered at $O$. Note that only the farthest points are picked up to create a connecting boundary of the polygon, so that the convexity is maintained.

The Gift-wrapping algorithm.

One can also use the Gift-wrapping technique to compute the convex polygon. Starting with a vector of points that is known to be on the convex hull, say, the point $O$, with the smallest $y$-coordinate, we sweep a half-polygon. We then march to $v_1$, repeat the same process, and find next vertex $v_2$. This process terminates when we reach $O$ again. This is similar to wrapping an object with rope. Finding the next vertex takes time proportional to the number of points remaining. Thus, total time is $O(n\mathcal{H})$, where $\mathcal{H}$ denotes the number of points in the convex polygon. This algorithm is more efficient (only $O(\log n)$), than Graham-scan algorithm, if the number of points on the convex polygon is small.

Theorem 4.2   The convex hull of a set $S$ of $n$ points in $\Re^k$ can be computed in $O(n\log \mathcal{H})$ time for $k=2$ or for $k=3$. Here, $\mathcal{H}$ is number of i-faces, $i = 0, 1, k-1$.

Figure: Gift wrapping Algorithm geometry.

Assuming all your polygons are in counter-clockwise order, the moment your non-initial polar angle makes left turn, you know it's not convex. You could see if the line segments intersect with each other to figure out if the polygon is complex. Note that, in the figure  the angles $\alpha_i \geq 180^\circ$.