### 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 _{0}*;

*p*;

_{1}*p*) of neighbor points, deletes point

_{2}*p*if it does not lie outside the line from

_{1}*p*to

_{0}*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.

_{2}

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 _{1}* lies outside the line from point

*p*to point

_{0}*p*, then the view will next be slid to the right; otherwise,

_{2}*p*is deleted, and the view will next be slid to the left (unless the view is at the beginning of the underlying list).

_{1}

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; } }