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

Question

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?

Answer 1

There are only three possible cycles. The path length option in the comment may well be your best bet. Below is another possibility but I doubt that the "crossing segments check" can outperform a straight forward length computation. It avoids taking square roots and can be implemented over the integers (if that is relevant) but in this day and age this should hardly matter. You'll have to try.

If segment 12 crosses segment 34 then take 1324. Else if segment 13 crosses 24 then take 1234. Else take 1243.

Segments $(p_1, p_2)$ and $(q_1, q_2)$ cross if and only if all entries in the cross product of the columns of the $3\times 2$ matrix $$\begin{pmatrix} p_1-p_2\\ q_1-q_2\\ p_2-q_1 \end{pmatrix}$$ have the same sign and its last entry has the largest absolute value. (Here points are interpreted as rows.) Of course if you do this in floating point then these criteria are less straight forward than they sound since subtraction is involved.

Answer 2

Let $${\bf z}_k=(x_k,y_k)\qquad(1\leq k\leq 4)$$ be the four points, arranged such that $$x_1\leq x_2\leq x_3\leq x_4\ .$$ This means that the leftmost point gets number $1$, the point with next-larger $x$-coordinate gets number $2$, and so on. The rightmost point gets number $4$.

It is assumed that no three of the four given points are collinear. In particular $x_1<x_4$, and the line $g$ connecting ${\bf z}_1$ with ${\bf z}_4$ is not vertical.

As an auxiliary tool we now introduce the affine linear function $$\phi(x,y):=(x_4-x_1)(y-y_1)-(y_4-y_1)(x-x_1)\ .$$ It is designed such that $\phi(x,y)=0$ when the point $(x,y)$ is on the line $g$. When the point $(x,y)$ is lying above $g$ then $\phi(x,y)>0$, and when $(x,y)$ is lying below $g$ then $\phi(x,y)<0$. Using this $\phi$ compute the test quantities $$t_2:=\phi(x_2,y_2), \qquad t_3:=\phi(x_3,y_3)\ .$$ The signs of these two quantities (they cannot be $=0$) decide how the subsequent connections should be drawn. Proceed as follows:

If $t_2\>t_3>0$ (meaning that ${\bf z_2}$ and ${\bf z}_3$ are on the same side of $g$) draw $\ {\bf z}_1\to{\bf z}_2\to{\bf z}_3\to{\bf z}_4\to{\bf z}_1$.

If $t_2\>t_3<0$ (meaning that ${\bf z_2}$ and ${\bf z}_3$ are on opposite sides of $g$) draw $\ {\bf z}_1\to{\bf z}_2\to{\bf z}_4\to{\bf z}_3\to{\bf z}_1$.

It helps to draw a figure in order to understand that this works in all nondegenerate cases. If three points on a line are allowed more work is necessary.