El volumen de la intersección de dos tetraedros

Question

En primer lugar, yo estoy lejos de ser un matemático, y esta pregunta puede ser fácil, si ese es el caso, por favor no dude en hacérmelo saber.

Supongamos que tengo 2 tetraedros (2 3D simplex), con conocidos ABCD y DEFG coordenadas en el espacio euclidiano.

Hay un algoritmo/enfoque sabe si este tetraedros se cruzan, y si es así saber el volumen de la intersección en un caso general?

Me imagino que la primera pregunta no es difícil de resolver, por ejemplo, comprobando si los 4 vértices de un tetraedro están dentro de la otra, pero no puede ser más inteligentes enfoques, por lo tanto voy a dejar la pregunta.

EDIT: Como se señaló en los comentarios, la intersección puede ser un poco más complicado de lo que yo suponía.

Answer 1

Aquí es un método que no es óptimo en términos de la cantidad de cosas para ver, pero es fácil de implementar...

Para detectar CUALQUIER intersección entre tetraedros a y B, usted sólo tiene que asegurarse de que se encuentra en el exterior de cualquier medio-espacio definido por las 4 facetas de B, y viceversa. Si este no es el caso, entonces hay una intersección. Esta prueba puede ser realizada por el orient3d predicado dar aquí. Esto es equivalente a la aplicación de la Hyperplane teorema de separación. Un método más rápido es de aquí con el código.

Para calcular el volumen de la intersección, usted necesita el límite de la representación de la intersección de volumen (en términos de vértices, aristas, caras, etc. en lugar de intersección de halfspaces que no decirle nada acerca de los vértices y cómo están conectados). La cosa más sencilla que se me ocurre es considerar todos 6 los bordes de B, y se cruzan con ellos en contra de Una, lo que resulta en 6 nuevos, posiblemente más corta y no la conexión de segmentos. El segmento tetraedro intersección es muy sencillo: se cruzan el segmento contra el plano que contiene la faceta y mantener la parte que está en el interior. Ahora, considere el 12 extremos de los 6 segmentos y calcular el casco convexo de los puntos. Para ello, me gustaría utilizar algo existente de la biblioteca de código como paquete qhull.. Alternativamente, usted puede tratar de poner en práctica por sí mismo utilizando los incremental método o algo más. El volumen se puede encontrar por la norma suma más de las facetas de una vez se ha calculado la intersección del límite de la representación.