Take the 2-minute tour ×


Point0: x=1; y=4;
Point1: x=199; y=45;
Point2: x=42; y=333;
Point3: x=444; y=444;
PointN: x=nnn; y=mmm;


| -----  |
| |    | |
| |----| | 
|        |


share|improve this question
it's not clear how you are deciding which points belong to which polygon.. could you please explain more? –  Jack Dec 8 '10 at 13:56
Polygon does not cross other polygons. –  jitm Dec 8 '10 at 14:08

2 Answers 2

up vote 4 down vote accepted

Idea: Find the convex hull of all the points. For all the points that do not belong to the hull repeat the algorithm until no points left.

share|improve this answer
Thanks a lot for your answer I have not thought about this algorithm. –  jitm Dec 8 '10 at 14:09

You could probably find a distance matrix for all the points and then do iterations like the following:

  1. Find the largest distance
  2. Draw rectangle for the two points which correspond to the found distance
  3. Remove these points from the list
  4. Repeat
share|improve this answer

Your Answer


