find diagonals of quadrilateral

Question

I have 4 points and need to determine which pairs of these points represent the diagonals.

In other words, I am trying to triangulate a quadrilateral.

I realize that triangulation of polygons is a well documented subject, but I'm looking for a short algorithm that I can implement in a few lines. Hopefully since I only have quadrilaterals, I can avoid importing a whole triangulation library.

Answer 1

There are three possible groupings of points into pairs that could form the two diagonals. For each of them, calculate the sum of the edge lengths:

\begin{align*} (p_1, p_2), (p_3, p_4) &:& \|p_2-p_1\|+\|p_4-p_3\|\\ (p_1, p_3), (p_2, p_4) &:& \|p_3-p_1\|+\|p_4-p_2\|\\ (p_1, p_4), (p_2, p_3) &:& \|p_4-p_1\|+\|p_3-p_2\| \end{align*} whichever has the highest sum on the RHS is the diagonals. This works in any dimension provided the four points are coplanar.

Answer 2

Find six distances,four sides and two diagonals from given points.For each of 20 ($ n C_r = 6 C_3 = 20 $) combinations taking three at a time use triangle in equality to determine which are the two diagonals, they are pairwise the largest side.

To do this sides inequality comparison there are 6 points out of which only two but not three points should be the same. Next with any of two of quadrilateral diagonals and two sides with common points there are two combinations for triangles lying on either side.

Answer 3

1. Pick random 3 points - they will represent first triangle.

2. Find its 'signed' square: $2\cdot S_{123} = x_1\cdot(y_2-y_3)+ x_2\cdot(y_3-y_1)+ x_3\cdot(y_1-y_2)$. It can be negative and we'll use it.

   ('signed' square shows if chosen points form clockwise rotation)

3. Now find $S_{124}$, $S_{134}$, $S_{234}$ using the similar formula.

4. Only one of 3 mentioned squares will have same sign as $S_{123}$ and then you can pick triangles $123$ and $abc$ where $abc$ are the indexes of that square.

Overall, you will need to find 4 expressions and check 3 cases in the worst case.

(the general idea is to find all possible triangle squares and compare their signs)

Answer 4

For a convex quadrilateral, the centroid $G$ always belong to the interior part. Hence you can rank your vertices $V_i$ according to $\operatorname{Arg}(V_i-G)$, then joint the first and the third, the second and the fourth ones.