¿Comprobar si un punto está en un plano? (Minimiza el uso de multiplicaciones y divisiones)

Question

En $\mathbb R3$, dado un avión $\mathcal P$ definido por tres puntos 3D de los puntos de $v_0, v_1, v_2$, quiero ver si otro punto de $p$ pertenece a ese plano, evitando el uso de multiplicaciones y divisiones tanto como sea posible.

La razón es para mitigar los errores de punto flotante incurridos por el equipo de representación de los números decimales.

---

Mi método actual es:

1. Calcular la forma general del plano de ecuación de $ax+by+cz+d=0$

   Donde $a,b,c$ son los componentes del plano de la unidad vector normal $N={(v_1-v_0)\times(v_2-v_0) \over \|(v_1-v_0)\times(v_2-v_0)\|}$

   Y $d=N.v_0$

2. Enchufe punto de $p$ en el plano de ecuación: $res=a.p_x+b.p_y+c.p_z-d$

   Si el resultado es null, el punto se encuentra en el avión

   Debido a errores de punto flotante, de hecho, me compruebe si el resultado es "casi" nula: $|res|<\epsilon$

Sin embargo, en ciertos casos, cuando la conecto $v_2$ en el plano de ecuación, me parece que no pertenecen al avión, a pesar de que solía $v_2$ para el cálculo de la ecuación en el primer lugar. (Puedo obtener un resultado más grande que mi $\epsilon$.)

Esto es debido a errores de punto flotante. Ver a mi pregunta sobre Stack Overflow: http://stackoverflow.com/q/21916606/143504

Así que estoy buscando un método alternativo que podrían reducir estos errores.

Answer 1

Cuatro puntos se encuentran en un plano común si el determinante

$$\begin{vmatrix} x_1 & x_2 & x_3 & x_4 \\ y_1 & y_2 & y_3 & y_4 \\ z_1 & z_2 & z_3 & z_4 \\ 1 & 1 & 1 & 1 \end{vmatrix}$$

es cero. Esto tiene la ventaja de que no requiere divisiones. Requiere bastante multiplicaciones, aunque.

Usted podría, no obstante, desea tener una mirada en Shewchuk de la página en la Adaptación de la Precisión Aritmética de Punto Flotante y Rápido Robusto Predicados de Geometría Computacional, donde se pueden encontrar artículos sobre cómo evaluar estos predicados exactamente, y también una implementación en C haciendo precisamente esto.

Como una alternativa, usted podría querer usar uno de CGALs exacta de los predicados de los núcleos.

Tenga en cuenta sin embargo que, si sus puntos de entrada son el doble de coordenadas, a continuación, un punto de mentir exactamente en un avión se extendió por otros tres es bastante improbable. Así que asegúrese de que usted no hace conceptuales errores.

Su declaración sobre el uso de $\epsilon$ la hora de interpretar el resultado muestra que usted es consciente de los valores numéricos imprecisión involucrados. Sin embargo, estoy seguro de cómo se había de decidir sobre qué valores de $\epsilon$ son razonables. Que puede depender de su aplicación. Sólo entonces se puede juzgar a la dirección en la que prefiere errar.