Description

The Simple Polgyon algorithm takes a set of n points and connects them to form a simple polygon.

Steps

Pseudocode

 pointsArray = getPoints();
 pivotPoint = get point with largest x-coord

 orderedPoints = []
 orderedPoints.add(pivotPoint);

 draw line vertical from pivot point

 while(orderedPoints.length < pointsArray.length) {
  point = (rotate line anti-clockwise
          around pivot until point reached)
  orderedPoints.add(point)
 }

 for each point 'p' in orderedPoints {
  if (p == last point) {
    // we can now complete the polygon
    join p with the first point in orderedPoints
  } else {
    join p with the next point in orderedPoints
  }
 }

 PointSet p = getPoints();
 simplePolygon(p);

 PointSet q = new PointSet(p.length);
 q[0..2] = p[0..2];

 int m = 2;

 for (int k = 3; k < p.length; k++) {
   while (next turn is a right turn) {
     m--;
   }
   q[++m] = p[k];
 }

 return q[0..m];

 Find two points p, q, on the convex hull
 with minimum and maximum y-coordinate respectively.

 Draw two horizontal lines (the "calipers")
 l1 and l2 through each of p and q.

 Set r=p and s=q //r and s will be
 the changing pivots of l1 and l2.

 let dMax = 0

 while ((r != q) or (s != p)) { 
   d = dist(r,s)
   if (d > dMax) {
     //current furthest pair to be updated
     furthestPoint1 = r
     furthestPoint2 = s
   }

   Rotate l1 around r and l2 around s,
   keeping l1 and l2 parallel, until
   caliper l meets point t on convex hull.

   if (l == l1) {
     r = t //change l1's pivot to t
   } else {
     s = t //change l2's pivot to t
   }

 }

 output furthestPoint1, furthestPoint2

 public double closestPair(PointSet p) {
  sortOnXCoord(p); // sort points in p on x-coordinate
  return cPRec(p, 0, p.length-1);
}

 private double cPRec (PointSet p, int i, int k) {
  double d;
  if (i == k) d = Double.MAX_VALUE;
  else {
    int j = (i+k)/2;   // mid-point of p[i..k]

    double mid =(p[j].x + p[j+1].x))/2.0; // x coord of mid-line
    Draw dividing line at x = mid

    double d1 = cPRec(p, i, j); // p[i..j] sorted on y coord
    double d2 = cPRec(p, j+1, k); // p[j+1..k] sorted on y coord

    merge(p, i, j, k); // p[i..k] sorted on y coord

    d = Math.min(d1, d2);
    Draw strip centered along the diving line of width 2*d

    PointSet s = filter(p, i, k, d, mid); // the points in the “strip”

    int m = s.length;  // no. of points in s
    for (int a=0; a < m-1; a++)
      for (int b=a+1; b <= Math.min(a+5,m-1); b++)
        if ( dist(s[a], s[b]) < d )
          d = dist(s[a], s[b]);
          Highlight line s[a] -> s[b] //as these points are now the new closest pair in this set

    }
    return d;
  }