13,447,284 members (37,669 online)
alternative version

#### Stats

68.4K views
33 bookmarked
Posted 11 Sep 2008

# Convex Hull

, 11 Sep 2008
Computing the convex hull of a given set of points

## Introduction

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.

## Background

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

#### The Algorithm

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
} ```

#### The Implementation

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)
{
render(); //render any point or edge if any
pID++;

graphics = this.CreateGraphics(); // create the graphics
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);
pointsList.Add(sp); //store it in the list
} ```

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)
{
// creates all possible segments from the points list
// as I mentioned in the algorithm
InitOrderdPoints();
// go compute the convex hull
Compute();
//prepare a new convex hull by clearing the points list and
//the convex segments list
prepareNewConvexHull();
}
else
{
MessageBox.Show(&quot;Pick the hull points&quot;);
}
} ```

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 will be the points that are not in  the current segment

ProcessingPoints = new List<SuperPoint>(pointsList);
//this loop prepares the ProcessingPoints list for each segment
for (j = 0; j < ProcessingPoints.Count; )
{
if(Segments[i].contains(ProcessingPoints[j]))
{
//eliminating the points that are already in the current segment...
//we don't need them
ProcessingPoints.Remove(ProcessingPoints[j]);
j = 0;
continue;
}
j++;
}

//checking if the current segment is an edge or notBy calling isEdge function
if(!isEdge(ProcessingPoints, Segments[i]))
{
Segments.Remove(Segments[i]);
i = 0;
continue;
}
else
{i++;}
}
//adding the segments and points to the lists to render
renderEdges(Segments);
List<SuperPoint> superPointsList = new List<SuperPoint>(pointsList);
List<Segment> segmentsList = new List<Segment>(Segments);
}```

The `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++)
{
if(isLeft(edge, processingPoints[k].P))
{
return false;
}
}
return true;
} ```

And the `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;
//The determinant
// | 1 px py |
// | 1 qx qy |
// | 1 rx ry |
//if the determinant result is positive the point is //left of the segment
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)
return false;

return true;```

In `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 `InitOrderdPoints()`, `prepareNewConvexHull()`, `render()` and `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.

## History

• 12th September, 2008: Initial post

## Share

 Software Developer Egypt
No Biography provided

## You may also be interested in...

 First Prev Next
 2D or 3D? B. L. Zeebub31-Dec-15 16:14 B. L. Zeebub 31-Dec-15 16:14
 My vote of 5 alekh168-Mar-13 8:23 alekh16 8-Mar-13 8:23
 Thanks yash5557-Oct-12 16:14 yash555 7-Oct-12 16:14
 My vote of 5 Pritesh Aryan8-May-11 23:05 Pritesh Aryan 8-May-11 23:05
 Refactoring and performance improvements Member 30097399-Dec-10 1:22 Member 3009739 9-Dec-10 1:22
 Hey, I used your convex hull algorithm implementation for displaying surface analysis. Thank you! I did some refactoring for the convex hull class : Exposed the class and compute method. //See usage example below ```[TestMethod]
public void TestConvexHull()
{
List points = new List();

ConvexHull convexHull = new ConvexHull(points);
var edges = convexHull.Calculate();
foreach (var item in edges)
{
if (((int)item.p.X == 5 && (int)item.p.Y == 5)
|| ((int)item.q.X == 5 && (int)item.q.Y == 5))
Assert.Fail("Convex Hull is not really working.");
}

}``` In additional I did some performance improvements: For 100 points the calculation takes 3 milliseconds and not 22001 milliseconds. ```public class ConvexHull

{

private static readonly log4net.ILog log =
log4net.LogManager.GetLogger(System.Reflection.MethodBase.GetCurrentMethod().DeclaringType);

#region Globals
List m_pointsList = new List();
List m_segments = new List();
int m_pID = 0;
#endregion

public ConvexHull(List points)
{
foreach (var item in points)
{
}
}

{
m_pID++;
SuperPoint sp = new SuperPoint(point, m_pID);
}

public List Calculate()
{
List returnValue = null;
if (m_pointsList.Count > 0)
{
Stopwatch stopwatch = new Stopwatch();
int countOfPoints = this.m_pointsList.Count;
stopwatch.Start();
InitOrderdPoints();
if (log.IsDebugEnabled)
log.DebugFormat("InitOrderdPoints. Count of points {0}, milliseconds {1}.", countOfPoints, stopwatch.ElapsedMilliseconds);
returnValue = Compute();
stopwatch.Stop();
if(log.IsDebugEnabled)
log.DebugFormat("Finished calculating convex hull. Count of points {0}, milliseconds {1}.", countOfPoints, stopwatch.ElapsedMilliseconds);
}
return returnValue;
}

#region Functions

private List Compute()
{
using (MethodLogger methodLogger = new MethodLogger(log, "Compute convex hull."))
{

List edges = new List();

foreach (var segment in m_segments)
{
if (isEdge(m_pointsList, segment))
}
return edges;
}
}

///
/// Iterates over all processingPoint and identify if current segment is edge.
///

///
///
///
private bool isEdge(List processingPoints, Segment edge)
{
for (int k = 0; k < processingPoints.Count; k++)
{
//ProcessingPoints will be the points that are not in the current segment
if (!edge.contains(processingPoints[k]))
{
if (isLeft(edge, processingPoints[k].P))
{
return false;
}
}
}
return true;
}

private bool isLeft(Segment segment, Vector2 r)
{
float D = 0;
float px, py, qx, qy, rx, ry = 0;
//The determinant
// | 1 px py |
// | 1 qx qy |
// | 1 rx ry |
//if the determinant result is positive then the point is left of the segment
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 <= 1)
return false;

return true;
}

private void InitOrderdPoints()
{
//Initialize all possible segments from the picked points
for (int i = 0; i < m_pointsList.Count; i++)
{
for (int j = 0; j < m_pointsList.Count; j++)
{
if (i != j)
{
Segment op = new Segment();
Vector2 p1 = m_pointsList[i].P;
Vector2 p2 = m_pointsList[j].P;
op.p = p1;
op.q = p2;

}
}
}
}

#endregion
}

#region Structures
public struct Segment
{
public Vector2 p;
public Vector2 q;

public bool contains(SuperPoint point)
{
if (p.Equals(point.P) || q.Equals(point.P))
return true;
return false;
}

public override string ToString()
{
return string.Format("Segment P: {0}, Q {1}", p, q);
}

}

public struct SuperPoint
{
public Vector2 P;
public int ID;

public SuperPoint(Vector2 p, int id)
{
P = p;
ID = id;
}

public override string ToString()
{
return string.Format("SuperPoint P {0}, ID {1}", P, ID);
}
}

#endregion
public struct Vector2
{
public float X;
public float Y;

public Vector2(float x, float y)
{
this.X = x;
this.Y = y;
}

public bool Equals(Vector2 ob)
{
Vector2 c = (Vector2)ob;
return X == c.X && Y == c.Y;
}

public override int GetHashCode()
{
return X.GetHashCode() ^ Y.GetHashCode();
}

public override string ToString()
{
return string.Format("Vector2 X: {0}, Y {1}", X, Y);
}
}

public struct Vector3
{
public float X;
public float Y;
public float Z;

public Vector3(float x, float y, float Z)
{
this.X = x;
this.Y = y;
this.Z = Z;
}

public override string ToString()
{
return string.Format("Vector3: X {0}, Y {1}, Z {2}.", X,Y,Z);
}
}``` Thanks again Daniel.Pashkov (Israel).
 using an sketch image input to compute extreme points using convex hull in c# aznimah12-Apr-10 1:23 aznimah 12-Apr-10 1:23
 Re: using an sketch image input to compute extreme points using convex hull in c# aznimah13-Apr-10 18:07 aznimah 13-Apr-10 18:07
 Last Visit: 31-Dec-99 18:00     Last Update: 18-Mar-18 12:25 Refresh 1