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 (p₀; p₁; p₂) of neighbor points, deletes point p₁ if it does not lie outside the line from p₀ to p₂, 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 p₁ lies outside the line from point p₀ to point p₂, then the view will next be slid to the right; otherwise, p₁ 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;
   }
}