Given a set of points: |
|
The resulting polygon is the smallest convex polygon that includes all the points given. |
Given a set of points:
1) Select the leftmost point 2) Sort remaining points by bearing (counter-clockwise) to leftmost point 3) Add these three points to the polygon 4) For every point after 3: 1) Calculate the angle between the second last point in the polygon, the last point in the polygon and this point 2) Remove the last point from the polygon until the angles makes only "left" turns 3) Add the point to the polygon
The resulting polygon is the smallest convex polygon that includes all the points given.