Imagine that you have a piece of wood and a number of metal pins come out from it randomly (as in the above image), and you picked up an elastic rubber band and open it wide with your hand to contain all the metal pins and let it go. You will observe that the elastic rubber band will shrink and snap around the metal pins (only the outer metal pins). These outer segments of the elastic band form the convex hull.
The Convex Hull of a given point P in the plane is the unique convex polygon whose vertices are points from P and contains all points of P. In other words, the convex hull of a set of points P is the smallest convex set containing P.
The convex hull is one of the first problems that was studied in computational geometry. In fact, convex hull is used in different applications such as collision detection in 3D games and Geographical Information Systems and Robotics.
Using the Code
Note: Suppose that the convex hull segments are ordered clockwise, then a convex hull segment is a segment that does not have any point on its left side. If a segment has at least one point on its left, then we eliminate in from the convex hull segments.
Input: Given a set of points P in the plane
Output: Convex Hull segments
Initialize all possible line segments between the given points:
For i = 0 to i < number of segments
For j = 0 to j < number of all points
get the points that are not in the current segment
Check if the segment is an Edge of the convex hull by
checking whether any of the points
Is located on its left
If it is not an edge remove it from the segment list and
reset the iterator i and continue
Else increment the iterator i and continue
We have a black background Windows Form.. this will be our plane that we are going to pick the hull points from. .. OK ? …
Picking points on the Form will fire the mouse down event in which we render our points and store the picked points in a list (we will use this list in the algorithm).
First let's see what is done in mouse down event:
private void frmConvexHull_MouseDown(object sender, MouseEventArgs e)
graphics = this.CreateGraphics();
renderPoint(e.X, e.Y, Color.Lime); render the picked point
PointF p = new PointF(e.X,e.Y);
SuperPoint sp = new SuperPoint(p,pID);
That will lead us to the
renderPoint() function. This function will render the point and something like a (sniper view of its target) around the point.
private void renderPoint(float x, float y, Color c)
Pen p = new Pen(c,1.7f);
graphics.DrawEllipse(p, x - 5, y - 5, 10, 10);
graphics.DrawLine(p, x, y - 5, x, y - 5 - 2.5f);
graphics.DrawLine(p, x - 5, y, x - 5 - 2.5f, y);
graphics.DrawLine(p, x, y + 5, x, y + 5 + 2.5f);
graphics.DrawLine(p, x + 5, y, x + 5 + 2.5f, y);
graphics.FillEllipse(Brushes.Lime, x - 1.25f, y - 1.25f, 2.5f,2.5f);
After we picked our points, we will proceed to compute their convex hull by pressing compute button... this will fire the
btnCompute_Click() event handler:
private void btnCompute_Click(object sender, EventArgs e)
if (pointsList.Count > 0)
MessageBox.Show("Pick the hull points");
Let's jump to the
Compute() function and see what happens there:
private void Compute()
List<SuperPoint> ProcessingPoints = new List<SuperPoint>();
int i = 0;
int j = 0;
for (i = 0; i < Segments.Count; )
ProcessingPoints = new List<SuperPoint>(pointsList);
for (j = 0; j < ProcessingPoints.Count; )
j = 0;
i = 0;
List<SuperPoint> superPointsList = new List<SuperPoint>(pointsList);
List<Segment> segmentsList = new List<Segment>(Segments);
Compute function will always jump to the function
isEdge to check if the segment is an edge or not:
private bool isEdge(List<SuperPoint> processingPoints, Segment edge)
for(int k = 0; k < processingPoints.Count; k++)
isEdge function will always jump to the function
isLeft to check if any of the points are located on the left of the segment or not.
private bool isLeft(Segment segment, PointF r)
float D = 0;
float px, py, qx, qy, rx, ry = 0;
px = segment.p.X;
py = segment.p.Y;
qx = segment.q.X;
qy = segment.q.Y;
rx = r.X;
ry = r.Y;
D = ((qx * ry) - (qy * rx)) - (px *(ry - qy)) + (py * (rx - qx));
if (D <= 0)
isLeft function, we will compute the determinant shown above in the function.
If the determinant result is positive, then the point is left of the segment then the function will return
true indicating that a point is left of the segment .. hence
isEdge will return
false hence that segment will be removed from the segments list …. And so on until the remaining segments in the segments list are the real segments of the convex hull... And Finished... I hope that helps.
I didn't explain some helper functions such as
renderEdges() etc., and GDI+ functions that are used in the code, because here we are concerned with just the algorithm of computing the convex hull.
Try it yourself ... download the source code and run the program.
- 12th September, 2008: Initial post