Dadas las coordenadas de los vértices de un cuadrilátero convexo, encuentra qué pares de vértices determinan las diagonales

Question

Estoy escribiendo un programa que tomará en cuatro $(x, y, z)$ puntos que forman un cuadrilátero, y producen dos conjuntos de $(x, y, z)$ puntos que forman los dos triángulos mayores que componen el cuadrilátero.

Estoy teniendo algunas dificultades para encontrar la manera de determinar qué puntos forman las diagonales del cuadrado. Evidentemente, si puedo averiguar dos puntos que formen una diagonal, los dos triángulos estarán formados por esos dos puntos más uno de los otros puntos restantes.

Así que, dados los cuatro puntos:

• $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)$

¿Cómo puedo determinar qué puntos forman una diagonal del cuadrilátero?

Answer 1

Creo que este enfoque es el más sencillo para los cuadriláteros 3D planos y convexos:

Suponga que tiene cuatro puntos $(A,B,C,D)$ y que quieres comprobar si AC es realmente una diagonal del cuadrilátero. Si lo es, los ángulos $\angle CAB$ y $\angle CAD$ tendrán diferentes orientaciones (en el sentido de las agujas del reloj).

Esto significa que los vectores $\vec{c}_1$ y $\vec{c}_2$ definidos como productos cruzados:

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

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

...serán ambas perpendiculares al plano del cuadrilátero $ABCD$ pero con direcciones opuestas . Esto significa que su producto escalar debe ser negativo:

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

El algoritmo es el siguiente:

$$\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}$$

Si $s<0$ , $AC$ es una diagonal del cuadrilátero.

Si no es así, debe intentarlo sólo una vez más, intercambiando los lugares por $C$ y $B$ (o $C$ y $D$ ). Si vuelves a fallar, $AD$ (o $AB$ ) tiene que ser una diagonal (no es necesario comprobarlo).

EDITAR: El método puede transformarse en código de software con bastante facilidad. Todos los cálculos son sencillos y no demasiado costosos. Y sólo hay una condición "si" en el camino.

Answer 2

Si el cuarilateral es convexo y plano, entonces esto funcionará.

Dados 4 puntos, hay 3 posibilidades que podrían ser las diagonales

• AB,CD
• AC,BD
• AD,BC

Supongamos que AB,CD son las diagonales, entonces la intersección de AB y CD se encuentra entre A y B, y también entre C y D. Puedes probar esto para las tres posibilidades, será cierto sólo para una.