Convex perimeter

Using the sorting algorithms previously presented it becomes very easy to treat some real-life problems. For example, you have many points(N=100, let’s say) and you want to determine the convex polygon surrounding them.

The easiest way is the following (Thanks to R. Sedgewick, Princeton):

1.Find the point  P with the lowest y coordinate.

2.Find the angles made by any point Q with the horizontal and sort the points based on this angle.

3.Add these ordered points to a stack, taking care that the last 3 point on the stack makes a counterclockwise angle. If this condition is not fulfilled, remove the n-1 point from the stack

The complexity is NlogN (previously my solution was n3).

The result looks like this:


Leave a Reply

Your email address will not be published. Required fields are marked *