# 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.

# First C Compiler Now on Github

The earliest known C compiler by the legendary Dennis Ritchie has been published on the repository.

# HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

HTML5 Mobile Development: Seven Good Ideas (and Three Bad Ones)

# Building Bare Metal ARM Systems with GNU

All you need to know to get up and running... and programming on ARM

# Amazon's Vogels Challenges IT: Rethink App Dev

Amazon Web Services CTO says promised land of cloud computing requires a new generation of applications that follow different principles.

# How to Select a PaaS Partner

Eventually, the vast majority of Web applications will run on a platform-as-a-service, or PaaS, vendor's infrastructure. To help sort out the options, we sent out a matrix with more than 70 decision points to a variety of PaaS providers.

More "Best of the Web" >>