No habrá una respuesta mágica a esta pregunta; en algún momento solo tendrás que asimilarlo y considerar todos los casos. Una vez tuve que calcular la intersección de un triángulo y un círculo ... fue horrible. Dado que su forma 3D tiene ciertas simetrías (como el hecho de que siempre es un prisma triangular) ayuda a reducir enormemente las posibilidades.
- Encuentra de qué lado del plano se encuentra cada punto.
- Si todos los puntos están en un lado, listo.
- Si un punto está separado de los otros 5 por el plano, la intersección es un triángulo. Presumiblemente, tiene información de conectividad que le indica qué caras son incidentes en el vértice, y puede calcular las 3 líneas debido a las intersecciones plano-plano, y luego el triángulo de intersección. Lo mejor es hacer todo esto en una parametrización del plano de intersección.
- Dos puntos están separados, o ambos están en la misma cara triangular del prisma, o son dos puntos correspondientes en caras triangulares opuestas. En cualquier caso, la intersección es un cuadrilátero.
- Por tres puntos, todos podrían ser la misma cara triangular o solo dos en ella. Tiene dos casos aquí, para un triángulo o hexágono resultante.
Esos son realmente los únicos casos de alto nivel, obviamente hay reducciones de simetría que debe aplicar (en el caso 5, el caso de un punto es equivalente al caso de 2 puntos en la otra faceta triangular).
Mi única sugerencia es elegir una representación sólida para sus formas y utilizar predicados sólidos para realizar las pruebas geométricas. Para el plano, se representa mejor como un punto en el plano y un vector unitario normal. El prisma se representa definiendo una base ortonormal (tríada) con un eje alineado con la dirección de extrusión del prisma. Deje que un vértice esté en el origen, los otros dos en la cara triangular se representen en las coordenadas uv de la tríada, y luego solo necesita almacenar su altura y el desplazamiento global de su vértice base. Básicamente, estoy pensando
struct plane{
double p[3]; // point on plane
double n[3]; // unit normal vector to plane
};
struct TriPrism{
double basis[9]; // 3x3 orthogonal matrix of local coordinate frame (det = +1)
// Stored columnwise, first two vectors are in the plane of the triangular face)
// Last vector is parallel to extrusion direction, call the set [u, v, w]
double base[3]; // global coordinates of base vertex (where the basis vectors are "rooted")
double buv[2]; // the uv-coordinates of the second point on the triangular face
double cuv[2]; // third point on triangular face
// Assume that the "bottom" triangular face is formed by vertices (a,b,c)
// with base being a, and (b-a) cross (c-a) directed along vector w (instead of against)
double h; // height of prism ("top" triangular face is h*w offset from the "bottom" face)
};
Esta representación es robusta para mover el prisma y debe mantener una alta precisión relativa para todos los casos, excepto los más patológicos.
En cuanto a los predicados robustos, recomiendo los predicados robustos de Shewchuk
suponiendo que use números de coma flotante ordinarios. Lo usarías principalmente orient3d.
En términos de representar el polígono de salida final, elija una parametrización adecuada del plano. La mejor opción, en mi opinión, es elegir primero una base ortonormal establecida en el plano, determinada por Gram-Schmidt en el vector normal del plano ( ver geom_maketriad3d aquí ). Luego, deje que el origen de ese plano paramétrico 2D sea la proyección del punto base del prisma en el plano. Esto garantiza que su parametrización esté realmente enraizada cerca de donde estará el polígono resultante, para garantizar el uso efectivo de los bits de los números de coma flotante involucrados. Realice todos los cálculos restantes utilizando esta parametrización si es posible.
En general, el cálculo geométrico está lleno de peligros debido a estas tontas consideraciones numéricas (un ligero error con un vértice cerca del plano en el caso 5 anterior podría cambiar drásticamente el resultado de un 4 gon a un 6 gon). Le sugiero que maneje algunos casos a la vez e intente visualizar el resultado. Aquí tengo un programa de visor bastante simple , con una especie de capacidad de lenguaje de entrada similar a la de postscript. Puede volcar las facetas del prisma y dibujar el plano y también dibujar los polígonos resultantes y verificarlos visualmente para ver si son correctos.
Anexo : Olvidé que originalmente quería el área del polígono de intersección. Es trivial, pero en caso de que no lo sepa, una vez que tenga la colección de líneas que definen los bordes del polígono en el plano de corte, debe convertirla en una representación de vértice. Dado que construyó las intersecciones a partir de intersecciones de plano frontal y plano, debería haber podido realizar un seguimiento del orden de las líneas y, por lo tanto, del orden de los bordes que rodean el polígono. Solo necesita calcular la intersección de pares sucesivos de estas líneas para obtener los vértices. Una vez que tenga los vértices, es sencillo obtener el área ( consulte, por ejemplo, geom_polygon_area2d aquí ). Si trabajó completamente en coordenadas uv del plano de corte, puede alimentarlos directamente a dicha función para obtener el área.
Debo agregar que existe un enfoque tonto obvio, que consiste en elegir una región grande adecuada en el plano de corte y muestrear puntos al azar y verificar si están en el prisma (que es barato, ya que es convexo). Luego, puede calcular el área como una relación de puntos dentro versus puntos totales, multiplicado por el área de la región de muestreo. Si realmente no le importa la precisión, entonces esto probablemente será más rápido, pero de lo contrario, el método analítico no debería ser mucho más lento, a pesar de su complejidad combinatoria.
