Merging convex hulls
Consider the following problem: given two convex polygons, what is the smallest convex polygon containing their union? The answer is the polygon corresponding to the merged convex hulls.
Merging convex hulls can be done in the trivial way: given all the vertices of both polygons, compute corresponding hull. More efficient algorithms exist, and involve finding the bridges between the polygons. The following figure illustrates this concept:
Two disjoint convex polygons. The merged hull consists of convex chains belonging to the polygons (shown is solid blue lines), joined by bridges between the polygons (shown in dashed blue lines)
Given two disjoint polygons, there exist two bridges between the polygons. When the polygons intersect, there may be as many as there are vertices, as illustrated below:
Two intersecting convex polygons. The merged hull consists only of bridges between the polygons (shown in dashed lines). There are eight bridges joining eight vertices.
The merge operation is at the heart of the divide-and-conquer approach. This applies to polygons as well. A very simple way to obtain the convex hull of a set of points is to divide the point set in two, and recursively compute the convex hulls of the two new smaller sets, and then merge them. Each set is again split, until the number of elements is small enough (say three or less) so that the convex hull may be trivially obtained.
Toussaint proposes using the Rotating Calipers to find the bridges between two convex polygons. The main advantage of his method is that it involves no backtracking, and the polygons can intersect. (Other algorithms require the polygons to be disjoint). The following result is the basis for his algorithm:
Given convex polygons P={p(1), ... , p(m)} and Q={q(1), ... , q(n)}, a pair of points (p(i), q(j)) form a bridge between P and Q if, and only if:
- (p(i), q(j)) form a co-podal pair.
- p(i-1), p(i+1), q(j-1), q(j+1), all lie to the same side of the line joining (p(i), q(j)).
Assuming the polygons are given in standard form and the vertices is clockwise order, the algorithm is as follows:
- Compute the vertices with maximum ycoordinate for both P and Q. If more than one exist, take the ones with greater x coordinates.
- Construct horizontal lines of support at these points, directed such that the polygons lie to their right (thus they point to the positive end of the x axis).
- Rotate both lines of support clockwise until one coincides with an edge. A new co-podal pair (p(i), q(j)) is determined. In the case of parallel edges, three co-podal pairs are determined.
- For all valid co-podal pairs (p(i), q(j)): check if p(i-1), p(i+1), q(j-1), q(j+1), all lie to the same side of the line joining (p(i), q(j)). If so, then the co-podal pair is a bridge, and is labelled as such.
- Repeat steps 3 and 4 until the lines of support reach their original position.
- All possible bridge pairs have thus been determined. Construct the merged convex hull by joining the proper convex chains between consecutive bridges.
The above result ensures the correctness of the algorithm. The running time is dominated by steps 1, 5 and 6, each running in O(N) time (where N is the total number of vertices). The algorithm therefore has linear time complexity.
A bridge between convex polygons determines in fact common tangents between the polygons, another useful concept. In addition, bridges are also at the heart of an algorithm computing the intersection between two convex polygons.
December 17th, 1998