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?
Best Answer
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.