Convex hull

Current action:

Left click on the canvas to apply the current action


What is the convex hull?

In geometry, the convex hull of a given set is the smallest convex set containing it. In the field of geometric algorithms, the convex hull of a finite set of points is very often used. In this case, the envelope is a convex polygon.

Incremental algorithm

Following the strategy of any incremental algorithm, this algorithm construct the convex hull of n points from the convex hull of n - 1points. Given a convex polygon (which is the convex hull of n - 1 points) and a point outside the polygon, the algorithm adds the new point as a vertex of the frontier of the new convex hull.

The algorithm proceeds as follows. First, sort the points lexicographically. Then proceed iteratively: given a point pi and the convex hull CHi-1 of the points p0,...,pi-1 , computes the supporting lines of the point pi and the convex hull CHi-1. Computing this supporting lines consists on finding the vertexs pl and pr of CHi-1 that pipl is the left supporting line of the CHi-1 and pipr is the right supporting line of CHi-1. Then, the algorithm deletes the chain pl,...,pr⊂CHi-1 and inserts the vertex pi.

Divide and conquer

This technique consists in subdividing recursively the problem in smaller subproblems, solve them and then merge the solutions of the subproblems to get the solution of the original problem.

In the case of the convex hull, the algorithm does the following operations. First orders the points lexicographically, like in the incremental algorithm.

Then, the recurrence starts. The algorithm divides the set S of the input points into to subsets Sa and Sb such that all points in Sa precedes lexicographically those of Sb and, in addition, |Sa| + |Sb| = |S| and ||Sa| - |Sb| ≤ 1. In this way, we obtain two subsets of similar size where each convex hull are disjoined. This last property will be relevant at the merge.

The convex hull CHa and CHb are computed recursivelywith the two subsets Sa and Sb, respectively.

In order to merge the two convex hulls and obtain the convex hull of the set S, the algorithm computes the common exterior tangents between CHa and CHb. Note that the vertical separation between Sa and Sb guarantees that CHa and CHb that are disjoint, and, therefore, their common exterior tangents are, in fact, two, one upper and the other lower. In fact, computing them consists in finding the vertexs pTa, pBa of CHa and pTb and pBb of CHb such that pTa pTb defines the upper tangent and pBapBb defines the lower tangent. The merge ends deleting the chains pBa,...,pTa ⊂ CHa and pBb,...,pTb ⊂ CHb and connecting pTa with pTb and pBa with pBb in order to form only one convex polligon, the convex hull of S.

Graham algorithm

This technique is also known as the gift wrapping. It consists in polygonize the set of points in a certain order and, as the polygonization progresses, gradually remove any "pockets" that may form, that is, the sub-polygons of the convex hull that are not part of the polygonization of the points that are being generated.

More specifically, first a point p is selected from the given set S, that it is certainly a point of the convex hull, taking, for example, the lexicographically minor point. Then, the rest of the points are ordered angularly from p. After that, the algorithm proceeds iteratively processing every point with the given order, and keeps at every step the convex hull of the points considered so far. For it, at the i-nth iteration, the algorithm part from the convex hull CHi-1 of the points p,p1,...,pi-1. If p=v1,...,vk denotes the vertexs of CHi-1, the algorithm checks if vk-1,vk,pi form a left turn. If so, CHi = CHi-1 ∪ pi. Otherwise, CHi = CHi-1 - vk and recursively is checked again the orientation of the turn vtop-1,vtoppi untill it is a left turn. Then, the convex hull is updated and the next point can be considered.

What are the Halton sequences?

The Halton sequences are very useful for generating random points on the plane (actually pseudo-random). This sequences are constructed with a deterministic method based on the coprime numbers. An example of constructing point in the square (0,1) X (0,1) ⊂ ℝ2 with bases 2 and 3, respectively, is as follows:

To generate the sequence of base 2, the space (0,1) is divided recursively in two halves, then four parts, then eight parts, etc.

1/2, 1/4, 3/4, 1/8, 5/8, 1/16, 9/16, ...

Similraly, in base 3 the interval (0,1) is recursively divided into thirds, obtaining the sequence:

1/3, 2/3, 1/9, 4/9, 7/9, 2/9, 5/9, 1/27, ...

Combining both sequences the following points are obtained in the square (0,1) X (0,1):

(1/2,1/3), (1/4,2/3), (3/4,1/9), (1/8,4/9), (5/8, 7/9) (3/8,2/9), (1/16,5/9), (9/16,1/27), ...