Email	Print Reprint
	add to:
	Del.icio.us Digg Google Furl	Slashdot Y! MyWeb Blink
	TABLE OF CONTENTS Introduction The Convex Hull and the Graham Scan The Details The Code Creating the Hull

Finding the Convex Hull of a set of points is an interesting problem in computational geometry. It is useful as a building block for a diverse set of applications, including things such as:

• Collision detection in video games, providing a useful replacement for bounding boxes.
• Visual pattern matching/object detection
• Mapping
• Path determination

Just as an example, consider if one of the Mars rovers has to chart a path around a boulder. The convex hull can be used to provide the shortest path past the obstacle, given a map that shows the points where the boulder abuts the ground.

In this article, I review the definition of the 2D convex hull, describe Graham's efficient algorithm for finding the convex hull of a set of points, and present a C++ program that you can use to experiment with the algorithm.

The Convex Hull

There are many ways to draw a boundary around a set of points in a two-dimensional plane. One of the easiest to implement is a bounding-box, which is a rectangle that spans the set from its minimum and maximum points in the X and Y planes.

Creating a bounding-box is easy, but it doesn't form as tight a wrapper as we might like around a set of points. Consider the bounding box around the three points in Figure 1.

You can certainly wrap those points much more tightly using easy-to-compute straight lines, and Figure 2 shows an example that is significantly more compact:

As it happens, Figure 2 is a convex hull.

So what is the definition of a convex hull? The common visualization analogy for a 2D convex hull is to imagine the set of points on the plane as nails pounded into a board. If you wrap the entire set in an appropriately sized rubber band, the band snaps into place, forming a convex hull, which is the minimum-energy wrapper that encloses all the points.

An informal definition that has a little more precision but is still easy to understand might say that the convex hull meets the following properties:

• The hull is a cycle graph whose vertices are composed of a subset of the the points in set S.
• No points in S lie outside the graph.
• All interior angles in the graph are less than 180 degrees.

1 Introduction | 2 The Convex Hull and the Graham Scan | 3 The Details | 4 The Code | 5 Creating the Hull Next Page

RELATED ARTICLES ComponentOne Releases Studio Enterprise 2008 v3 Debugging API Spec for Power Architecture Released Amazon SimpleDB: Unlimited Public Beta Announced CodeGear RAD Studio 2009 Released Measuring Parallel Performance: Optimizing a Concurrent Queue		TOP 5 ARTICLES No Top Articles.