# Convex-Hull Algorithms: Implementation, Testing, and Experimentation
## 4 Implementations
### Plane Sweep
Unfortunately, the description given in [15] does not lead to an efficient implementation; the goal of that article was to show that an in-place implementation is possible. The problem with stable partitioning can be avoided by performing the computations in a different order: find the west and east poles before sorting. This way, when creating the two candidate collections, we can use unstable in-place partitioning employed in quicksort--for example, the variant proposed by [PERSON] ([26], Section 7.1)--and sort the candidate collections separately after partitioning. Let \(p\) and \(r\) be two points that are known to be on the convex hull. In our implementation of plane-sweep the key subroutine is chain: It takes an oriented line segment \(\overrightarrow{p\mskip-4.0 mu r}\) and a candidate collection \(C\) of points, which all lie on the left of \(\overrightarrow{p\mskip-4.0 mu r}\), and computes the convex chain, i.e., part of the convex hull, from \(p\) to \(r\) via the points in \(C\). The extreme points are specified by two iterators and the candidate collection is assumed to follow immediately after \(p\) in the input sequence. The past-the-end position of the candidate collection is yet another parameter. To make the function generic, so that it can compute both the upper hull and the lower hull, it has a comparator as its last parameter. This comparator specifies the sorting order of the points. As is customary in the C++ standard library, a less-than comparison function orders the points in non-decreasing order and a greater-than comparison function orders them in non-increasing order. To accomplish its task, chain works as follows: (a) If \(C\) is empty, return the position of the successor of \(p\) as the answer, i.e., the computed chain consists of \(p\). (b) Sort the candidates in the given order according to their \(x\)-coordinates. As a result, the points with equal \(x\)-coordinates can be arranged in any order. (c) If in \(C\) there are points with the same \(x\)-coordinate as \(p\), eliminate all the other except the one having the largest \(y\)-coordinate--with respect to the given ordering--before any further processing. (d) Use the standard backtracking procedure [33] to eliminate all concave points from the remaining candidates. The stack is maintained in place at the beginning of the zone occupied initially by \(p\) and coming just after \(p\). This elimination process is semi-stable, meaning that it retains the sorted order of the points in the left part of partitioning; it may change the order of the eliminated points. (e) Return the position of the first eliminated point as the answer (or the past-the-end position of \(C\) if all points are convex). Thus, our in-place implementation of plane-sweep processes any non-empty sequence of points as follows (for an illustration, see Figure 2):  
1. Find the west and east poles by scanning the input sequence once. Place the poles at their respective ends of the input sequence. If the poles are the same point, stop and return the position of the successor of the west pole. 2. Partition the input sequence into two parts: (a) the upper-hull candidates, i.e., the points that are above or on the line segment determined by the west pole and the east pole; and (b) the lower-hull candidates, i.e., the points below that line segment. 3. Apply the function chain with the poles, the upper-hull candidates, and comparison function less than. This gives us the upper hull from the west pole to the east pole, excluding the east pole. Figure 2: In-place plane-sweep algorithm illustrated. Swap the east pole to the beginning of the lower-hull candidates, and apply the function chain with the two poles--this time giving the east pole first, the lower-hull candidates, and the comparison function greater than. After this we also have the lower hull, but it is not in its final place. 5. Move the computed lower hull just after the computed upper hull (if it is not there already). This is a standard in-place block-swap computation.