Given X, a set of points in 2D, the Convex Hull is the minimum set of points that define a polygon containing all the points of X. If you imagine the points as pegs on a board, you can find the Convex Hull by surrounding the pegs by a loop of string and then tightening the string until there is no more slack, the Convex Hull is the pegs in contact with the string.

The following is an example of a Convex Hull of 20 points.

One way to compute a Convex Hull is to use the QuickHull algorithm. Starting with two points on the convex hull (the points with lowest and highest position on the x axis, for example), you create a line which divides the remaining points into two groups. If you find the Convex Hull of these two groups, they can be combined to form the Convex Hull of the entire set. Given the line and the set of points on one side of the line, we find the point in the set furthest from the line. This point will also be on the Convex Hull. Using this point and the two end points of the line, we can define two new lines on which we can recurse. If we find a line with one or no points on the outside of the hull we have constructed so far, then we stop knowing that both end points of the line and the one exterior point (if it exists) are in the Convex Hull.

The algorithm can be parallelized by running the recursive steps in parallel. The following code implements the QuickHull algorithm and a parallel QuickHull using the Task Programming Model.

One might be surprised to see how little extra code is necessary to turn a sequential algorithm into a parallel one. This is because the Task Programming Model takes care of many of the confusing, messy, and bug prone aspects of threaded programming.

We now create some points to try the QuickHull algorithm on:

$\mathrm{points}\u2254\mathrm{table}\left(\right)colon;\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{while}\left(\mathrm{numelems}\left(\mathrm{points}\right)1000\right)\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{do}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}p\u2254\left[\mathrm{RandomTools}:-\mathrm{Generate}\left(\mathrm{float}\left(\mathrm{range}equals;-1..1\right)\right)comma;\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathrm{RandomTools}:-\mathrm{Generate}\left(\mathrm{float}\left(\mathrm{range}equals;-1..1\right)\right)\right]semi;\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{if}\left(p\left[1\right]ast;p\left[1\right]plus;p\left[2\right]ast;p\left[2\right]1\right)\mathbf{then}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathrm{points}\left[\mathrm{numelems}\left(\mathrm{points}\right)\right]\u2254psemi;\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}semi;\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathbf{end}colon;\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathrm{points}\u2254\left[\mathrm{entries}\left(\mathrm{points}comma;apos;\mathrm{nolist}apos;\right)\right]colon;\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}t\u2254\mathrm{time}\left[\mathrm{real}\right]\left(\right)colon;\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathrm{QuickHull}\left(\mathrm{points}comma;\mathrm{plot}\right)semi;\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathrm{tSeq}\u2254\mathrm{time}\left[\mathrm{real}\right]\left(\right)-tcolon;\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}$

| |

Now try the parallel algorithm on the same set of points:

$t\u2254\mathrm{time}\left[\mathrm{real}\right]\left(\right)colon;\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathrm{QuickHull}\left(\mathrm{points}comma;\mathrm{plot}comma;\mathrm{parallel}\right)semi;\phantom{\rule[-0.0ex]{0.0em}{0.0ex}}\mathrm{tPara}\u2254\mathrm{time}\left[\mathrm{real}\right]\left(\right)-tcolon;$

As you can see, the relatively simple modification to add parallelism to the QuickHull algorithm leads to a good speed enhancement.