Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

# The C5 Generic Collection Library

### A Convex Hull Example

The convex hull of a point set is the smallest convex set containing all the points; see Figure 3. The convex hull can be described by a set of corner points of the point set. The classic algorithm for finding the convex hull works by sorting all the points, splitting them into a lower and an upper list (separated by the dashed line in Figure 3), and then scanning each list. The scanning considers triples (p0; p1; p2) of neighbor points, deletes point p1 if it does not lie outside the line from p0 to p2, then goes on to consider the next triple of points. For efficiency, this algorithm should be implemented using linked lists to hold the items (points). If an array list were used, then each point deletion would require sliding of all subsequent points in the array, which is slow.

Figure 3: Convex hull of a point set. The dashed arrow separates the lower and upper point lists. The grey points will be deleted during scanning of the lists; the black remaining points are the "corner" points that span the convex hull.

Then how should we access the items in the linked list? Item access by index is very slow, but we don't want client code to handle individual linked-list nodes (as in the standard .NET LinkedList<T>), because then we have to prevent such code from violating all sorts of invariants—a list node should belong to exactly one list, lists should not be circular, and so on. The C5 solution to this problem is to use slidable list views to access list items in constant time, whether in linked lists or in array lists.

In Listing Two, list contains a sequence of points, and view is a sublist view comprising three points. The while loop executes so long as there are more points in the list. If the middle point p1 lies outside the line from point p0 to point p2, then the view will next be slid to the right; otherwise, p1 is deleted, and the view will next be slid to the left (unless the view is at the beginning of the underlying list).

```IList<Point> view = list.View(0, 0);
int slide = 0;
while (view.TrySlide(slide, 3))
if (Point.Area2(view[0], view[1], view[2]) < 0) // right turn
slide = 1;
else { // left or straight
view.RemoveAt(1);
slide = view.Offset != 0 ? -1 : 0;
}
}```
Listing Two

### More Insights

 To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.