Sunday 19 December 2010

Andrew's Monotone Chain Convex Hull algorithm

This algorithm constructs convex hull of a set of 2D points. 
  1. Sorts points based on their X coordinate,
  2. Selects two points which contain minimum and maximum of X coordinate (P1, P2) from all points,
  3. Divides the set of points into two sub-sets (upper and lower hull) based on the line between point P1 and point P2,
  4. Processes points on per hull basis to detect points which have to be used to create a convex polygon.

Example of usage:

Source code:

Useful links:

1 comment: