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.

It so happens I'm dealing with convex quadrilaterals but it would be nice if the algo didn't depend on this. — Bob Woodley, Dec 28 '14 at 21:48

Jack D'Aurizio · Answer 1 · 2014-12-28T22:29:47.937

1

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.

edited Dec 28 '14 at 22:29

answered Dec 28 '14 at 18:17

Jack D'Aurizio

353,855

@user7530: you're right. Second part removed. – Jack D'Aurizio Dec 28 '14 at 22:30

user7530 · Accepted Answer · 2014-12-28T21:53:14.783

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.

edited Dec 28 '14 at 21:53

answered Dec 28 '14 at 18:19

user7530

49,280

1

(p1,p3),(p2,p4) is not also a possible answer? – Bob Woodley Dec 28 '14 at 21:42
Ah yes, you're right. One flip is required to find a non-intersecting pair of edges, to do the reverse you have to check both flips. Fixed. – user7530 Dec 28 '14 at 21:49

Narasimham · Answer 3 · 2014-12-28T17:55:45.217

0

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.

edited Dec 28 '14 at 17:55

answered Dec 28 '14 at 17:43

Narasimham

40,495

The diagonals are not always the largest side. Consider these points for example: (0,0), (10,0), (5,1), (5.001,1). – Bob Woodley Dec 28 '14 at 21:45

score 0 · Answer 4 · edited Jun 12 '20 at 10:38

Pick random 3 points - they will represent first triangle.
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)
Now find $S_{124}$, $S_{134}$, $S_{234}$ using the similar formula.
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)

I like this, but what it the points are not 2 dimensional points? I'd have to do a projection or a rotation, etc. — Bob Woodley, Dec 28 '14 at 21:46

find diagonals of quadrilateral

4 Answers4