Left click on the canvas to apply the current action
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.
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
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
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.
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), ...