Não haverá uma resposta mágica para esta pergunta; em algum momento, você apenas precisará absorver e considerar todos os casos. Uma vez eu tive que calcular a interseção de um triângulo e um círculo ... foi horrível. Como sua forma 3D tem certas simetrias (como o fato de ser sempre um prisma triangular) ajuda a diminuir tremendamente as possibilidades.
- Encontre qual lado do plano está cada ponto.
- Se todos os pontos estiverem de um lado, pronto.
- Se um ponto é separado dos outros 5 pelo plano, a interseção é um triângulo. Presumivelmente, você tem informações de conectividade para dizer quais faces são incidentes no vértice e pode calcular as 3 linhas devido às interseções plano-plano e depois ao triângulo de interseção. Melhor fazer tudo isso em uma parametrização do plano de interseção.
- Dois pontos são separados, ou ambos estão na mesma face triangular do prisma ou são dois pontos correspondentes em faces triangulares opostas. Nos dois casos, a interseção é quadrilateral.
- Por três pontos, todos poderiam ter a mesma face triangular ou apenas dois. Você tem dois casos aqui, para um triângulo ou hexágono resultante.
Esses são realmente os únicos casos de alto nível, obviamente existem reduções de simetria que você precisa aplicar (no caso 5, o caso de um ponto é equivalente ao caso de 2 pontos na outra faceta triangular).
Minha única sugestão é escolher uma representação robusta para suas formas e usar predicados robustos para realizar os testes geométricos. Para o plano, é melhor representado como um ponto no plano e um vetor normal unitário. O prisma é representado pela definição de uma base ortonormal (tríade) com um eixo alinhado com a direção de extrusão do prisma. Deixe um vértice estar na origem, os outros dois na face triangular sejam representados nas coordenadas uv da tríade e, em seguida, você só precisará armazenar sua altura e o deslocamento global de seu vértice base. Essencialmente, estou 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)
};
Essa representação é robusta para movimentar o prisma e deve manter alta precisão relativa para todos os casos, exceto os mais patológicos.
Quanto aos predicados robustos, eu recomendo os predicados robustos de Shewchuk,
assumindo que você use números de ponto flutuante comuns. Você usaria principalmente orient3d.
Em termos de representação do polígono de saída final, escolha uma parametrização adequada do plano. A melhor opção, na minha opinião, é primeiro escolher uma base ortonormal definida no plano, determinada por Gram-Schmidt no vetor normal do plano ( veja geom_maketriad3d aqui ). Então, deixe a origem desse plano paramétrico 2D ser a projeção do ponto base do prisma no plano. Isso garante que sua parametrização esteja realmente enraizada perto do local onde estará o polígono resultante, para garantir o uso efetivo dos bits dos números de ponto flutuante envolvidos. Faça todos os cálculos restantes usando essa parametrização, se possível.
Geralmente, a computação geométrica é repleta de perigos devido a essas considerações numéricas tolas (um pequeno erro com um vértice próximo ao plano no caso 5 acima pode alterar drasticamente o resultado de 4-gon para 6-gon). Sugiro que você lide com alguns casos de cada vez e tente visualizar o resultado. Eu tenho um programa visualizador bastante simples aqui , com um tipo de recurso de linguagem de entrada semelhante ao postscript. Você pode despejar as facetas do prisma e desenhar o avião e também desenhar os polígonos resultantes e verificá-los visualmente para ver se estão certos.
Adendo : esqueci que você originalmente queria a área do polígono de interseção. É trivial, mas caso você não saiba, depois de ter a coleção de linhas que define as arestas do polígono no plano de corte, você deve convertê-lo em uma representação de vértice. Desde que você construiu as interseções a partir das interseções de plano de faceta e plano, você deve ter conseguido acompanhar a ordem das linhas e, portanto, a ordem das arestas ao redor do polígono. Você só precisa calcular a interseção de pares sucessivos dessas linhas para obter os vértices. Depois de ter os vértices, é simples obter a área ( veja, por exemplo, geom_polygon_area2d aqui ). Se você trabalhou inteiramente nas coordenadas uv do plano de corte, é possível alimentá-las diretamente para essa função para obter a área.
Devo acrescentar que existe uma abordagem burra óbvia, que é escolher uma região grande adequada no plano de corte e amostrar aleatoriamente pontos e verificar se eles estão no prisma (o que é barato, pois é convexo). Em seguida, você pode calcular a área como uma proporção de pontos dentro de pontos totais versus pontos, vezes a área da região de amostragem. Se você realmente não se importa com a precisão, provavelmente será mais rápido, mas, caso contrário, o método analítico não deve ser muito mais lento, apesar da complexidade combinatória.
