Dgdrxrt

I have a four points in plane and need to test (based on point coordinates) whether they are able to form a convex quadrilateral:

Of course, the test should avoid configurations like these:

Given the diagonals, I can check whether the quadrilateral is convex (simply checking whether the intersection of diagonals is between both ends of both diagonals).

The real problem is how to label the four points and filter out all concave and degenerate configurations (like, for example: $A=B$).

If the labeling is possible (convex case found), the four points should be labeled such that $AC$ and $BD$ are diagonals of a convex quadrialteral.

I wonder if there is an elegant solution (rather than testing every possible permutation of $A, B, C$ and $D$).

You want to know whether all four points are vertices of their convex hull. So find the convex hull using say Jarvis's march and check whether it has four vertices. You'll have to decide what to do when three points are collinear.

If no points are coincident and only one angle between the vertices rays is greater than 180, then it is concave. Concave quadrilaterals can never form a bow tie. If all the angles between vertices rays are less than 90 degrees, then you have a bow tie. To order the points of a convex quadrilateral, average the vertices to find a median point. Draw a ray from the median point to each vertices. Calculate the angle of each median ray, and sort the vertices by their ray angles. Max to min sorting gives a clockwise quadrilateral, while min to max gives a counter clockwise quadrilateral.

Maybe a simpler way to solve this problem would be to write down the four vectors which describe the sides of the polygon, and calculate at each vertex the angle between these vectors. If this angle is ever obtuse, then you don't have a convex polygon. This procedure would only require going through 4 calculations.

Maybe it's too late for an answer to be useful to the OP (7 yrs too late!), but it still might be useful to someone.

My solution would be to get the barycentric coordinates (how?) of the fourth point, in the triangle formed by the first 3 points, and then using those coordinates to determine where the 4th point is relative to the triangle.

Now all we need to do is make sure that D lies in one of the green areas:

Vector2[] GetQuad(Vector2 a, Vector2 b, Vector2 c, Vector2 d)

 // make sure that points A, B and C don't form a degenerate triangle
 Vector2 ab = b - a;
 Vector2 bc = c - b;
 if (ab.Cross(bc) == 0)
 return null; // a, b and c are co-linear

 // Compute barycentric coordinates of point D relative to the triangle ABC
 Vector3 barycentric = Barycentric(d, a, b, c);
 float alpha = barycentric.x, beta = barycentric.y, gamma = barycentric.z;

 // now resolve...
 if (alpha < 0 && beta > 0 && gamma > 0) // d lies in the top-right green area
 return new Vector2[] a, b, d, c ;
 else if (alpha > 0 && beta < 0 && gamma > 0) // d lies in the bottom green area
 return new Vector2[] a, b, c, d ;
 else if (alpha > 0 && beta > 0 && gamma < 0) // d lies in the top-left green area
 return new Vector2[] a, d, b, c ;
 else
 return null;