Convex Hull

• Download ConvexHull - 45.73 KB

Introduction

Imagine that you have a piece of wood and a number of metal pins comes 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 forms the convex hull

Background  

The Convex Hull of a given points 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 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 in clockwise then a convex hull segment is a segments that don’t have any point on its left side. If a segment have at least on 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 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 lets 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 some thing 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("Pick the hull points");
    }

 }
 

Lets 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]))
        {
          //eleminating 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);
   renderingPoints.Add(superPointsList);
   renderingEdges.Add(segmentsList);
}

         


 

The Compute function will always jump to the function isEdge to check if the segments 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 is located on the left of the segment ot 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 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 remaning segments in the segments list are the real segments of the convex hull...  And Finidhed... I hope that helps

  
I didn’t explaine some helpers functions such as InitOrderdPoints(),prepareNewConvexHull(),render() and renderEdges()..etc , and GDI+ functions that is used in the code, cause we are concerned here with just the algorithm of computing the convex hull.

Try it your self ... download the source code and run the program ..