Distancia entre dos polígonos convexos en 3D

Question

Tengo dos polígonos convexos en 3D. Ambos son planos en diferentes planos, por lo que son un par de caras.

¿Cuál es la forma más sencilla de calcular la distancia más cercana entre estos dos polígonos?

Editar: La longitud de la línea más corta posible que tiene un punto final en el primer polígono y otro punto final en el segundo polígono. La distancia que estoy buscando es la longitud de esta línea lo más corta posible.

Answer 1

Esta es una optimización limitada simple con restricciones lineales y una función de objetivo cuadrático. Hay muchos algoritmos que se pueden usar, como el descenso de gradiente.

Answer 2

Pasa por todos los vértices del primer objeto, luego en ese bucle, recorre todos los vértices del segundo objeto. En tu ciclo más interno, compara la distancia entre los dos vértices actuales y almacena la distancia más baja. Lo hago de esta manera todo el tiempo y siempre y cuando no tengas una malla ridículamente grande, es casi instantáneo.

Answer 3

No está claro lo que has intentado.

This parece probable para los segmentos per se.

Entonces, todo lo que tiene que hacer es verificar todos los pares de aristas. Me gustaría implementar eso primero antes de tratar de optimizar.

Probablemente haya una optimización al considerar el vector de un centroide al otro y solo considerando los bordes que están en algún sentido en esa dirección.

Answer 4

Bueno, solo hay unas pocas posibilidades; la línea más corta entre los dos polígonos podría ser:

1. entre dos vértices
2. entre un borde y un vértice
3. entre dos bordes (imaginar dos polígonos en planos perpendiculares)
4. entre un vértice y el interior del polígono
5. O los polígonos se cruzan

Caso s 1-3 se tratan cuidando cada borde + par de vértices como un segmento de línea y enumerando el distance between all line-segment pairs.

Para el caso 4, busque el distance between each vertex and the other polygon's plane. Verifique para asegurarse de que la línea (que abarca desde el vértice hasta el punto más cercano en el plano) se encuentre dentro del otro polígono; si no es así, entonces la línea más corta que la otra polígono estará en su perímetro, que ya fue atendido en el caso 1 o 2.
(asegúrese de hacer esta comprobación para ambos polígonos)

Para el caso 5, al menos un segmento de línea debe intersecarse con el área del otro polígono; si se intersectaran en sus perímetros, ya lo habríamos capturado en los casos 1-3, y si un vértice intersectó el área, tendríamos lo atrapó en el caso 4. Así que simplemente verifique intersection of each edge with the other polygon's plane y vea si el punto de intersección está dentro del otro polígono.
(asegúrese de hacer esta comprobación para ambos polígonos)

Tome la distancia mínima que se encuentra en todo eso, y hemos terminado.

Answer 5

Lo que la mayoría de la gente ha propuesto en este hilo es "tomar todos los puntos/bordes de un polígono y compararlos con cada punto/borde del otro". Esto probablemente funcionará bien si todo lo que haces es comparar dos polígonos bastante simples y si no estás demasiado preocupado con hacer esto rápidamente.

Sin embargo, si desea un método bastante fácil y mejor. Utilice, como lo sugiere Ben Voigt, un método de optimización cuadrático (es decir, Quadratic Programming). Básicamente, sus polígonos son su conjunto de restricciones lineales, es decir, su punto de solución debe estar hacia el lado interno de cada borde de su polígono (eso es una restricción de desigualdad). Y su función de costo para optimizar es solo la distancia euclidiana, es decir, la Q en la formulación estándar es solo la matriz de identidad. Una vez emitido como un problema así, puede usar una biblioteca que resuelva esto (hay muchos de esos por ahí), o puede estudiarlo desde un libro y rodar su propio código (es un algoritmo bastante fácil de codificar)

Si desea un método real para hacer esto, por ejemplo, si esa simple prueba de polígono a polígono es el primer paso hacia formas 3D más complejas (como un sólido hecho de polígonos). Entonces, lo más probable es que solo uses un paquete que ya lo haga. Here es un conjunto de bibliotecas de detección de colisiones, muchas de las cuales tienen una profundidad de penetración o, lo que es equivalente, una distancia mínima.