Given a set of (x,y) coordinates, give the set of edges to draw a simple polygon

Question

Let's say I give you the following array of points:

(1,1) (1,3), (2,2), (4,1), (4,3)

My (terrible) mspaint drawing of the shape that would be created by these looks like this:

How, given an arbitrary set of coordinates, can I define the edges which constitute a shape with no overlapping edges?

Answer 1

A copy from the highest voted answer from SO:

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

I understand this is really late, but it might be useful for future viewers.