Channels ▼
RSS

.NET

The C5 Generic Collection Library

Source Code Accompanies This Article. Download It Now.


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


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips 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.
 

Video