4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Is your quadrilateral guaranteed to be convex? $\endgroup$ – Wouter Sep 25 '18 at 7:04
  • $\begingroup$ Yes, the quadrilateral will be convex. $\endgroup$ – ImpromptuMusic Sep 25 '18 at 7:05
  • $\begingroup$ Is it also planar? $\endgroup$ – Wouter Sep 25 '18 at 7:26
  • $\begingroup$ Yes, the quadrilaterals will all be planar, not skewed. $\endgroup$ – ImpromptuMusic Sep 25 '18 at 8:13
  • $\begingroup$ 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. $\endgroup$ – Narasimham Oct 4 '18 at 18:58
6
$\begingroup$

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

enter image description here

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Blue Sep 25 '18 at 14:28
  • $\begingroup$ @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 :) $\endgroup$ – Oldboy Sep 25 '18 at 14:41
  • $\begingroup$ "Make it work, then make it pretty." :) $\endgroup$ – Blue Sep 25 '18 at 14:43
  • $\begingroup$ @Blue 1) Make it work 2) Make it work correctly 3) Make it work fast. In software industry steps 2) and 3) are optional. $\endgroup$ – Oldboy Sep 25 '18 at 14:53
  • $\begingroup$ Fantastic! Thanks for the help! $\endgroup$ – ImpromptuMusic Sep 26 '18 at 6:57
0
$\begingroup$

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
  • AD,BC

Suppose AB,CD are the diagonals, then the intersection of AB and CD lies between A and B, and also between C and D. You can test this for all three possibilities, it will be true for just one.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.