how to arrange 4 cartesian points in clockwise or anti-clockwise order

Question

I am implementing a program in C which requires that given 4 points should be arranged such that they form a quadrilateral.(assume no three are collinear)
Currently , I am ordering the points in the order of their slope with respect to origin.
See https://ibb.co/cfDHeo .
In this case a,b,c,d are in descending order of slope but on joining a to b , b to c , c to d , d to a - I don't get a quadrilateral .
So my method fails in such cases.

I need suggestion.

Thanks.

Answer 1

There are many ways to order the points, especially if they form on concave polygon. For this case, the problem is easy. Say you have points $a,b,c,d$ in this order. Check the intersection between the two diagonals, $ac$ and $bd$, as segments, not infinite lines. That means that the intersection is between $a$ and $c$. If it is, you have a convex quadrilateral. If not, you have two options: it is either a concave quadrilateral, or the sides intersect, like in your case. Either way, if you swap any adjacent points (say the first two), you will get a quadrilateral. So $bacd$ in your case is OK. If you swap points on a concave quadrilateral you get a different concave quadrilateral.

Answer 2

You can just order them by the angle from the centroid to each point, measured from the $+x$ direction. The Atan2 function does this nicely. The resulting quadrialteral may not be convex, but it will not be self-intersecting.