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?


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.
