Comprobar si un segmento de línea está por encima de otro en $\mathbb{R}^3$

Question

Hay dos segmentos de recta no paralelos $U$ y $V$ en $\mathbb{R}^3$ dadas cada una por sus dos puntos extremos $u_0, u_1$ y $v_0, v_1$ tales que si se proyectan en $\mathbb{R}^2$ por su $x$ y $y$ coordenadas, se cruzan. Queremos saber si la línea $U$ está por encima de $V$ . Más exactamente, supongamos que sus proyecciones sobre $\mathbb{R}^2$ se cruza en el punto $(x, y)$ . Queremos saber si el $z$ coordenadas del segmento de línea $U$ en el punto $(x, y)$ es mayor que el $z$ coordenadas del segmento de línea $V$ en el punto $(x, y)$ .

Suponiendo que $u_0, u_1, v_0, v_1$ son todos puntos de celosía, ¿hay alguna forma de hacerlo que no calcule explícitamente el $x$ , $y$ y $z$ ¿Coordenadas? En otras palabras, ¿cómo comprobar esto sin aritmética de coma flotante?

Motivación

Esto surge cuando estoy intentando calcular el casco convexo 3D de la proyección de una triangulación de polígono de $\mathbb{R}^2$ en $\mathbb{R}^3$ durante el cálculo de la triangulación delaunay ponderada del conjunto de puntos.

Answer 1

Creo que esta condición hace el trabajo: $$ 0 \le \det\left[\begin{matrix} v_0-u_0 & u_1-u_0 & v_1-v_0 \end{matrix}\right] \det\left[\begin{matrix} P(u_1-u_0) & P(v_1-v_0) \end{matrix}\right] \tag{$ \ast $} $$ Aquí $P$ es la proyección de coordenadas sobre $xy$ -plano; la matriz $\left[\begin{matrix} a & b \end{matrix}\right]$ es la matriz con los vectores $a$ y $b$ como columnas; el primer determinante es $3\times3$ y la segunda es $2\times 2$ . (Obsérvese que este último determinante es un subdeterminante del primero, por lo que hay alguna oportunidad de reutilizar resultados computacionales).

Para derivar esto, considere el siguiente método para resolver el problema directamente calculando $x,y,z$ . Primero hallamos la intersección de las proyecciones resolviendo el sistema $$ P(u_0) + s(P(u_1)-P(u_0)) = P(v_0) + t(P(v_1)-P(v_0)) \tag1 $$ A continuación, calculamos el $z$ coordenadas y compararlas: $$ u_{0z} + s(u_{1z}-u_{0z}) \mathrel{\stackrel{?}{\le}} v_{0z} + t(v_{1z}-v_{0z}) \tag2 $$ Si se resuelve el sistema (1) utilizando la regla de Cramer y se obtienen los resultados de $s$ y $t$ en (2), verá que es equivalente a ( $\ast$ )... suponiendo que no haya cometido algún error elemental.

(Geométricamente, ( $\ast$ ) es comprobar la lateralidad del tetraedro formado por los cuatro vértices).