Algorithms

Akl-Toussaint (AT)

the CGAL-1.2 implementation of the throw-away-algorithm by Akl and Toussaint [AT]. It starts by computing the 4-gon¹ spanned by the extreme points in $$x- and $$y-directions. Points inside this 4-gon are thrown away, the others are assigned to subproblems corresponding to the edges of the 4-gon. To solve a subproblem, points assigned to the subproblem are sorted and subhulls are then computed using Graham's scan. The implementation uses a predicate called Right_of_line to check sideness with respect to a line, two predicates to compare points lexicographically (one with preference to $$x-coordinate, one with preference to $$y-coordinate) for computing the initial points and sorting points in the subproblems, and a leftturn predicate to check orientation of three points. Internally STL-containers of type vector<Traits::Point_2> are used, i.e., points are copied, not pointers to points.² The sorting is done using the sort routine from the STL coming with the compiler.

waste Akl-Toussaint (wAT)

like Akl-Toussaint, but now 4 arrays are used to maintain pointers to points. Each array allocates space for $$n pointers, where $$n is the number of input points. That's why we call this variant waste.

waste Akl-Toussaint 8 (wAT8)

like waste Akl-Toussaint, but now initially an 8-gon is computed in order to discard points. The additional points are the extreme points in the diagonal directions of the Cartesian coordinate system. For this task, two additional predicates are used.

Graham-Andrew (GAw)

Andrew's variant [Aw] of the Graham scan [G]. All points are first sorted lexicographically. By a Graham scan over the sorted sequence of points, the subhull below the line segment from smallest to largest point is computed, and then by a scan in reverse order the subhull above that segment. During the scan, the heuristic described in [Me] is used.

Graham-Anderson (GAs)

Anderson's variant [As] of the Graham scan. The lexicographically smallest point $$w is computed. Then all points are sorted in rotation order around $$w, where ties are resolved by (inverse) distance to $$w. A predicate is used to do comparison with respect to the rotation order around $$w. In all tested traits, this predicate was implemented using the orientation test. Finally, a Graham scan over the sorted sequence is done.

Handley (Ha)

as suggested by Handley [Ha], this algorithm mixes discarding and sorting points. First extreme points in $$x-direction are computed. The goal of the next step is to compute the lower hull. Incrementally points are inserted in an (unbalanced) binary search tree starting with the extreme points computed initially, where in each step while walking down the tree points are discarded if they lie above the line segment through their current neighbors in the subsequence inspected so far. After processing all points a Graham scan over the sorted subset of points is done. The upper hull is computed analogously. The implementation internally maintains pointers to points.

Handley-Anderson (HAs)

applies the idea of mixing discarding and sorting points to Anderson's variant of the Graham algorithm. Comparison of points is with respect to the rotation order around the lexicographically smallest point.

Bykat (By)

CGAL implementation of Bykat's algorithm [By], which is a two-dimensional quickhull algorithm just like Eddy's algorithm [Ey, OvL]. The algorithm initially computes the two extreme points in $$x-direction and partitions the point set into the set of points above this line and the set of points below it. This gives rise to two subhull problems. In general, a subproblem to be solved in a quickhull step has an associated line segment, whose endpoints $$p and $$q are extreme points, and a associated set of points, which are candidates for extreme points between the segment endpoint. A subproblem is processed as follows: If the associated point set is not empty, the point $$r with maximum distance to the line segment is computed. Points inside the triangle spanned by the line segment $$pq and $$r are thrown away. The set of remaining points is partitioned according to the segment between $$p and $$r. This way, two new subproblems are formed. In contrast to the implementation of Eddy's algorithm, this version is non-recursive. Internally, STL-vectors are used for stack and point containers. Furthermore, STL-algorithms like partition are used to re-arrange points in the containers.

Eddy (Ey)

CGAL implementation of Eddy's algorithm [Ey]. Analogous to Bykat, but subproblems are solved recursively. Internally, STL-lists are used.

Jarvis (Ja)

CGAL implementation of Jarvis's march [J]. Starting with an initial extreme point, subsequent hull points are computed one by one by computing the minimum point with respect to rotation order around the so far last computed hull point. Uses the same predicate for rotation order as Graham-Anderson.

Incremental (IC)

Slightly modified and parameterized version of the LEDA convex hull algorithm using incremental construction. Besides a test for equality of points it uses an orientation predicate only.

Footnotes

1	might be degenerate, i.e. a triangle, a line segment, or even a point (if all input points are equal)
2	Of course, using an appropriate traits class, you can always let the algorithm maintain pointers instead of points.