A convex hull is a smallest convex polygon that surrounds a set of points. If you imagine the points as pegs sticking up in a board, think of a convex hull as a rubberband wrapped around them.
This program demonstrates several useful techniques.
It uses an AngleValue function to order the points. It uses the numeric value dy / (dy + dx) to order the angle from one point to another with respect to the horizontal. This number is not the angle itself, but it has the property that AngleValue(A) < AngleValue(B) if Angle(A) < Angle(B).
The program starts with a point guaranteed to be on the convex hull. For example, the point with the smallest Y coordinate. Then it begins sweeping around to find the point with the smallest AngleValue. It adds that point to the hull and repeats the sweep from the new point starting with the sweep angle it used in the last test. This process continues until the program finds the start point again.
To use the program, click several times to select points. Right click when you are finished. Use the Convex Hull menu item to find the convex hull.
Invoke the Hull Cull menu item to find the convex hull more quickly. This version finds the points closest to the corners of the form. They have the largest and smallest coordinate sums X + Y, X - Y, -X - Y, and -X + Y. These points are guaranteed to be in the convex hull. Notice that the points inside the trapezoid defined by these points are guaranteed to not be in the convex hull. Finding those points is non-trivial but finding the biggest rectangle that fits inside the trapezoid is easy. It is then easy to discard the points within the rectangle. This culling step means the convex hull algorithm must check many fewer points. The difference will be small in typical tests but can be large for a big data set.
Hover the mouse over part of the form and press F4 to invoke the AngleValues menu item. It displays the AngleValue for each point with respect to the mouse position.
For more information on graphics programs in Visual Basic, see my book Visual Basic Graphics Programming.
Thanks to Sylvain Ross for pointing out a bug. If two or more points are tied for the smallest Y coordinate, then the program needs to start its sweep using the one with the smallest X coordinate. Otherwise it does not necessarily find the starting point when it has finished building the convex hull.
Look here for Sylvain's page about convex hull computation in a .NET application. It is French but the code is in VB.NET with English comments.
| 
