How to connect a line between 4 randomly placed points on a plane such that the line does not cross itself

You get 4 coordinates of points on a plain. You need to connect them all with a line. The line must not cross itself.

What's your strategy?

See image Example

My first intuition was to organize the points as "Top left", "Top right", "Bottom left" and "Bottom right" and continue to connect them so that the top left goes to the bottom left, the bottom left to the bottom right, the bottom right to the top right, and the top right connects back to the top left.

This works in most cases, but not in all. Is there a better strategy?

Thank you all.

Solution

Take three points and form a clockwise triangle (compute the area as the cross product of two sides - if negative, swap two vertexes).

The take the fourth point and compute the areas of the triangles it forms with every (oriented) side of the former. When you find a negative area, insert the new vertex in this side and you are done.

It can turn out that you find no negative area, meaning that the fourth point is inside the triangle. You can insert it in any side.

enter image description here

if Area(P0, P1, P2) < 0
  Swap(P0, P1)

if Area(P0, P1, P3) < 0
  Solution: P0-P3-P1-P2
else if Area(P1, P2, P3) < 0
  Solution: P1-P3-P2-P0
else if Area(P2, P0, P3) < 0
  Solution: P2-P3-P0-P1
else
  Solution: P0-P1-P2-P3

UPDATE

You can think of it using the so-called locus approach. Assume you have formed and oriented a triangle and wish to insert the fourth point. Selecting an edge where you would insert, you can sketch all places where insertion will not cause the sides to cross.

enter image description here

Seeing the shape of the allowed region, you observe that it is the union of the half plane against the insertion side, and the original triangle.

The three lines of support of the triangle partition the plane in 7 regions. Inside any region, you have the choice between 1, 2 or 3 possibilities of insertion in a side (on the figure, we are in a region of type 1).

This apparently contrived approach shows you that you must compare the fourth point against the triangle sides (area test), and in the worst case you can't avoid comparing against the three of them.

The shape of the boundaries tell you what kind of equations you will need to use, and the number of regions hints you how many tests you will have to perform.