# Given coordinates of vertices a convex quadrilateral, find which pairs of vertices determine the diagonals

I'm writing a program that will take in four $$(x, y, z)$$ points that form a quadrilateral, and produce two sets of $$(x, y, z)$$ points that form the two largest triangles that comprise the quadrilateral.

I'm having some difficulty in coming up with a way to determine which points make up the diagonals of the quad. Obviously if I can figure out two points that are guaranteed to make up a diagonal, the two triangles will be comprised of those two points plus one of the other remaining points.

So, given four points:

• $$A = (x_A, y_A, z_A)$$
• $$B = (x_B, y_B, z_B)$$
• $$C = (x_C, y_C, z_C)$$
• $$D = (x_D, y_D, z_D)$$

How can I determine which points form a diagonal of the quadrilateral?

• Is your quadrilateral guaranteed to be convex? – Wouter Sep 25 '18 at 7:04
• Yes, the quadrilateral will be convex. – ImpromptuMusic Sep 25 '18 at 7:05
• Is it also planar? – Wouter Sep 25 '18 at 7:26
• Yes, the quadrilaterals will all be planar, not skewed. – ImpromptuMusic Sep 25 '18 at 8:13
• Find areas of all four possible triangles. In one combination if sum of triangles $ABC,BCD$ equals that of $BAD,ADC$ then $BC,AD$ are the required diagonals. Else try other combination. – Narasimham Oct 4 '18 at 18:58

I think this approach is the most straightforward for planar, convex, 3D quadrilaterals:

Suppose that you have four points $$(A,B,C,D)$$ and that you want to check if AC is really a diagonal of the quadrilateral. If it is, the angles $$\angle CAB$$ and $$\angle CAD$$ will have different orientations (cunterclockwise/clockwise).

This means that vectors $$\vec{c}_1$$ and $$\vec{c}_2$$ defined as cross products:

$$\vec{c}_1=\vec{AC}\times\vec{AB}$$

$$\vec{c}_2=\vec{AC}\times\vec{AD}$$

...will be both perpendicular to the plane of the quadrilateral $$ABCD$$ but with opposite directions. This means that their scalar product must be negative:

$$s = \vec{c}_1 \cdot \vec{c}_2 < 0$$

So the algorithm goes as follows:

$$\vec AC=(x_C-y_A)\vec{i}+(y_C-y_A)\vec{j}+(z_C-z_A)\vec{k}=p_1\vec{i}+q_1\vec{j}+r_1\vec{k}$$

$$\vec AB=(x_B-x_A)\vec{i}+(y_B-y_A)\vec{j}+(z_B-z_A)\vec{k}=p_2\vec{i}+q_2\vec{j}+r_2\vec{k}$$

$$\vec AD=(x_D-x_A)\vec{i}+(y_D-y_A)\vec{j}+(z_D-z_A)\vec{k}=p_3\vec{i}+q_3\vec{j}+r_3\vec{k}$$

$$\vec{c}_1=\vec{AC}\times\vec{AB}=(q_1r_2-q_2r_1)\vec{i}+(r_1p_2-r_2p_1)\vec{j}+(p_1q_2-q_2p_1)\vec{k}=c_{1x}\vec{i}+c_{1y}\vec{j}+c_{1z}\vec{k}$$

$$\vec{c}_2=\vec{AC}\times\vec{AD}=(q_1r_3-q_3r_1)\vec{i}+(r_1p_3-r_3p_1)\vec{j}+(p_1q_3-q_3p_1)\vec{k}=c_{2x}\vec{i}+c_{2y}\vec{j}+c_{2z}\vec{k}$$

$$s=\vec{c1}\cdot\vec{c2}=c_{1x}c_{2x}+c_{1y}c_{2y}+c_{1z}c_{2z}$$

If $$s<0$$, $$AC$$ is a diagonal of the quadrilateral.

If not, you should try only once more, swapping places for $$C$$ and $$B$$ (or $$C$$ and $$D$$). If you fail again, $$AD$$ (or $$AB$$) has to be a diagonal (you don't have to check that).

EDIT: The method can be transformed into software code fairly easy. All computations are straightforward and not too expensive. And there is only one 'if' condition along the way.

• Note that you needn't necessarily compute all of $s$: the sign of any one (non-zero) term $c_{1\star}c_{2\star}$ is all you need in order to determine whether the vectors point in opposite directions. Also note that you needn't actually compute each $c_{1\star}$ as an exact value: all you need to know is whether it's positive/negative/zero. That said, introducing the necessary logic handling on a CPU may be less performant than simply throwing the full vector calculations at a GPU. – Blue Sep 25 '18 at 14:28
• @Blue: You are right, there is a lot of room for optimization, the part which I skipped. Thanks for spotting that. I do like to optimize the software, but I always try to make it work first :) – Oldboy Sep 25 '18 at 14:41
• "Make it work, then make it pretty." :) – Blue Sep 25 '18 at 14:43
• @Blue 1) Make it work 2) Make it work correctly 3) Make it work fast. In software industry steps 2) and 3) are optional. – Oldboy Sep 25 '18 at 14:53
• Fantastic! Thanks for the help! – ImpromptuMusic Sep 26 '18 at 6:57

If the quarilateral is convex and planar, then this will work.

Given 4 points, there are 3 possibilities that might be the diagonals

• AB,CD
• AC,BD