Create non-intersecting polygon passing through all given points

Question

Suppose I have an array of points in random order, and I need to find a polygon (by sorting them, such that every adjacent pair represents a side) which passes through all of the points, and its sides are non-intersecting of course.

I tried to do it by selecting a point, and adding all points to the final array which are below it, sorted left to right. Then, adding all points which are above it, sorted right to left.

I've been told that I can add an additional point and sort naturally to avoid self-intersections.. I am unable to figure out that though. What's a simple way to do this?

Answer 1

Our strategy is to make a plan where we are sure that the polygon includes all points, and that we can find an order to connect them where none of the lines intersect.

Algorithm:

1. Find the leftmost points p
2. Find the rightmost point q
3. Partition the points into A, the set of points below pq, and B, the set of points above pq [you can use the left turn test on (p,q,?) to determine if a point is above the line].
4. Sort A by x-coordinate (increasing)
5. Sort B by x-coordinate (decreasing).
6. Return the polygon defined by p, the points in A, in order, q, the points of B in order.

Runtime:

Steps 1,2,3 take O(n) time.
Steps 4,5 take O(nlogn) time.
Step 6 take O(n) time.
Total runtime is O(nlogn).

Correctness:

By construction, all points besides p,q are in set A or set B. Our output polygon from line 6 therefore outputs a polygon with all the points. We now need to argue that none of the line segments in our output polygon intersect each other.

Consider each segment in the output polygon. The first edge from p to the first point in A can't intersect any segment (because there is no segment yet). As we proceed in order by x-coordinate through the points in A, from each point, the next segment is going to the right, and all previous segments are to the left. Thus, as we go from p, through all the points of A, to point q, we will have no intersections.

The same is true as we go from q back through the points of B. These segments cannot intersect each other because they proceed from right to left. These segments also cannot intersect anything in A because all points in A are below line pq, and all points in B are above this line.

Thus, no segments intersect each other and we have a simple polygon.

Source: Broken link