Minimum Convex Polygon Algorithm

The challenge is to write an algorithm which starts out with a list of points and returns an ordered list of those points which make up the vertices of a polygon which contains all of the points. This polygon must have the minimum possible area, and should not include three consecutive points which are on the same line.

The algorithm I used to solve this problem works like this:

polygon = pointWithMinimumXCoordinate();
points.removePointWithMinimumXCoordinate();
while(points.hasMorePoints()) {
   farthestPoint = null;
   maximumDistance = 0;
   foreach point in points {
      foreach side in polygon {
         minimumDistance = HUGE_NUMBER;
         if (distanceFromPointToSide(point, side) < minimumDistance) {
            minimumDistance = distanceFromPointToSide(point, side);
         }
      }
      if (minimumDistance < maximumDistance) {
         farthestPoint = point;
         maximumDistance = minimumDistance;
      }
   }
   polygon.insert(farthestPoint);
   points.removePointsContainedBy(polygon);
}

In english, that boils down to these easy steps:

  1. Start your polygon with the farthest left point.
  2. Do these steps until you run out of points:
    1. Find the point which is farthest from the closest side of the polygon.
    2. Insert that point between the vertices of the polygon that make that closest line.
    3. Remove any points from the list which now lie inside the polygon.
  3. Print out the vertices of the polygon

How To Use

  1. Download the zip file.
  2. Unzip it into a directory
  3. Make sure you are running java 1.5.0 or better:
    > java -version
  4. cd to the directory where you unzipped the zip file.
  5. Run the program:
    > java -jar MinimumConvexPolygon.jar test/points-005.txt
  6. Each time you click the mouse in the GUI, the program will advance one step.
  7. If you want to run the program and just get the vertices of the polygon as output, run it like this:
    > java -jar MinimumConvexPolygon.jar test/points-005.txt -command

Please feel free to mess around with the source code in the "src" directory, but be warned, it is just cobbled together and not very well structured or documented yet.