Submitted by Kevin Farnham on

I was browsing the examples that are part of the Threading Building Blocks source code download, seeking an example that illustrates how to apply the `concurrent_vector`

component, and my `grep`

executions brought me to the *examples/parallel_reduce/convex_hull* directory. This directory contains the source code for two programs that apply the QuickHull algorithm to solve convex hull problems.**What's a "convex hull"?**

I had never heard of a "convex hull" (aside from one on a boat) before I started looking at this example code, but it's an interesting class of mathematical problem. The Wikipedia convex hull entry provides the figure below, and the following explanation:

For planar objects, i.e., lying in the plane, the convex hull may be easily visualized by imagining an elastic band stretched open to encompass the given object; when released, it will assume the shape of the required convex hull.

Tim Lambert, lecturer for the School of Computer Science and Engineering at the University of New South Wales (Australia), describes a convex hull as follows: *"The convex hull of a set of points is the smallest convex set that includes the points. For a two dimensional finite set the convex hull is a convex polygon."* Tim provides a nice Java applet that lets you play with a set of points (move them, add new points, delete points) to visually understand the nature of a two-dimensional convex hull. Try it out!**Solving for a two-dimensional convex hulls**

Thinking about this mathematically, how would we proceed to solve for the convex hull? In the 2D case, you could select three points at random, creating a triangle, then you could extend the polygon by adding points that are outside of the triangle, which would then become a quadrilateral, then a 5-sided figure, etc. This sounds fine, but there is a problem: the solution must be a convex figure. Simply adding points to the figure as I described would not guarantee that the final result will be a convex figure. To guarantee a convex result, we'd need to add a check at each step to ensure that the new bounding figure did not have any concave areas; if it does have a concave area, the point that creates the concavity would have to be removed from the current solution.

If you work with Tim Lambert's 2D convex hull demo, you may be able to see what I'm talking about, and what I'm picturing in my head as I invent "Kevin's method for solving convex hull problems." After a bit of searching, I see that my method is somewhat like the algorithm Tim presents on his incremental algorithm page.

To see a visual demonstration of several methods for solving convex hull problems, visit Tim Lambert's Convex Hull Algorithms page. The Wikipedia's Convex hull algorithms page also introduces several algorithms for solving convex hull problems. I don't see my method anywhere on these pages, so it must not be a very efficient method!**The QuickHull algorithm for convex hulls**

The Threading Building Blocks convex hull example applies the QuickHull algorithm for solving convex hull problems. Once again, Tim Lambert helps us understand how this method works through his QuickHull algorithm page and applets. Jay Martin Anderson, Professor of Computer Science at Franklin and Marshall College (U.S.), tells us that:

The "QuickHull" algorithm is so named because of its similarity to the QuickSort algorithm. The algorithm is recursive, and, at each step of the algorithm, points are identified which are internal, and therefore never again are needed for the vertices of the convex hull.

**Next up: the TBB QuickHull implementation**

Now that we understand the problem at hand, we're ready to start looking at some code. In my next post I'll begin exploring the *convex_hull_sample* program that is provided with the TBB source code download. Subsequently, I'll also look at the *convex_hull_bench* program, which provides for side-by-side benchmarking between a "TBB unbuffered push_back" version of the QuickHull algorithm and the "TBB buffered" version of the algorithm (which is implemented in *convex_hull_sample*).

Kevin Farnham

O'Reilly Media

TBB Open Source Community

## Comments (2)

TopIntel Software ... said on

Jim,

You might also try posting your question to the TBB forum at: http://software.intel.com/en-us/forums/intel-threading-building-blocks/

-Lexi

Intel(R) Software Network Support

Anonymous said on

I am trying to locate available C# source code or a C# code library to solve the convex hull problem. Input will be a cluster of individual LIDAR points projected into the 2D (x, y) plane. I need to solve the convex hull problem as a pre-requisite to solving the convex/concave boundary problem.

Can you point me to such an available C# source/library solving the convex hull problem?

Thanks for your time and consideration.

Jim Dow

## Add a Comment

Top(For technical discussions visit our developer forums. For site or software product issues contact support.)

Please sign in to add a comment. Not a member? Join today