Como posso adicionar e subtrair polígonos convexos?

Eu tenho dois polígonos 2D convexos que se sobrepõem . Estou procurando um algoritmo para subtrair e adicioná- los. O resultado deve ser um único polígono côncavo ou (melhor ainda) um conjunto dos maiores convexos que formam o resultado côncavo (por exemplo, triângulos).

( Esquerda: os polígonos sobrepostos iniciais. Meio: O polígono côncavo resultante após a adição. Direita: Um conjunto de polígonos convexos que formam o resultado côncavo. Aqui seria melhor obter polígonos convexos maiores que um triângulo por razões de desempenho. Uma subtração do dois polígonos sobrepostos levariam à mesma imagem da esquerda, mas com a área sobreposta não fazendo parte do polígono resultante.)

Como posso fazer isso?

TL; DR Você precisa implementar operações booleanas usando árvores BSP.

Bem, parece que estamos falando sobre geometria sólida construtiva aqui. Eu implementei o CSG em nível comercial, então eu sei uma coisa ou duas sobre isso.

O artigo clássico sobre CSG é chamado Mesclando árvores BSP produz operações de conjunto poliédrico , para ser honesto, é demais para explicar aqui, mas, brevemente, o algoritmo lida com polígonos que ficam no mesmo plano de um particionamento de espaço binário, basicamente construindo uma árvore BSP de cada malha poligonal. O segundo passo é mesclar essas árvores do BSP; você simplesmente pega uma árvore e a insere na outra. O algoritmo passa a explicar como lidar com cada nó folha para dividir e subtrair os nós; nós que não forem necessários na forma final serão removidos; outros receberão o pai apropriado.

Mas espere! Esse artigo está falando basicamente de malhas poligonais e planos 3D, NÃO?

O algoritmo pode ser generalizado em qualquer dimensão, portanto, no seu caso 2D, é fácil usar segmentos de linha em vez de plano como as partições binárias. Portanto, cada polígono será convertido em uma árvore BSP e os dois serão mesclados. Por fim, você percorre a árvore resultante para gerar o polígono final,

Observe que esse algoritmo e o CSG em geral não lidam com faces de renderização e malha diretamente e não estão realmente prontos para renderização; portanto, você precisa extrair as faces das árvores finais do BSP. Também acho o traçado de raios uma abordagem mais fácil para renderizar o resultado CSG; você só precisa que os raios atravessem a árvore em vez de extrair e realmente dividir as faces (lembre-se de que lidamos apenas com partições binárias).

Em relação à robustez numérica. É bom notar que existem dois tipos de cálculos geométricos,

• Aqueles que são baseados na construção, você constrói uma forma com base no resultado de uma operação anterior. Por exemplo, y = sqrt(x)e depois use yem uma nova operação. Isso é chamado de construção; o problema é que erros numéricos se acumulam rapidamente.
• Como alternativa, existem operações que usam predicados , essencialmente, em vez de usar construção, você simplesmente pergunta se uma condição é verdadeira / falsa e usa o mesmo valor em operações diferentes. Os testes clássicos incluem o incircle e o teste de orientação; isso também é suspeito de erros numéricos, especialmente se você usar precisão simples ou dupla, mas geralmente fornecerá resultados muito melhores. existem outras soluções que variam em velocidade e precisão. Aqui está um dos trabalhos recentes que evitam a construção usando uma geometria baseada em plano para fornecer resultados precisos. Também cito o artigo:

O conceito de representação em plano de malhas poligonais foi descrito pela primeira vez por Sugihara e Iri [SI89]. Esse tipo de representação fornece uma vantagem importante quando se trata de tarefas que envolvem a alteração da topologia de sólidos representados por malhas, como a avaliação de expressões booleanas: nenhuma nova informação de geometria primária precisa ser construída para obter o poliedro resultante

E, finalmente, gostaria de acrescentar que, se você deseja iniciar a implementação do BSP CSG, recomendo iniciar nas perguntas frequentes do BSP .

Indo pelo seu exemplo:

Escolha um vértice inicial no polígono A e comece a verificar as arestas que se cruzam no sentido horário (ou anti-horário). Se não houver uma interseção, adicione o vértice anterior ao polígono resultante. Se houver uma interseção, adicione o ponto no qual eles se cruzaram ao polígono resultante e comece a iterar sobre o polígono B, na mesma ordem de enrolamento. Faça o mesmo, trocando novamente para o polígono A se ocorrer uma interseção.

Depois de acumular todos os vértices do novo polígono, execute um algoritmo de triangulação nele. O método de recorte de orelha é fácil de implementar, mas existem opções mais rápidas por aí.

Importante: verifique se o vértice no qual você começa não está dentro do outro polígono (verifique este artigo para obter pontos nos testes de polígono).

Iterar sobre cada aresta, para verificar se há uma interseção, seria um algoritmo O (n ^ 2). Você pode acelerá-lo localizando primeiro os vértices que estão dentro do outro polígono, pois as arestas vinculadas a esses vértices serão as que se cruzam.

Se você deseja um polígono côncavo , basta escolher a aresta mais próxima entre os dois polígonos de entrada e adicionar duas novas arestas:

Convexo fica um pouco mais complicado:

Uma abordagem é iterativa, pois adiciona vértices do segundo polígono ao primeiro, um de cada vez, evoluindo o primeiro polígono para um contêiner que engloba tudo.

Basicamente:

• Iterar através dos vértices do segundo polígono.
• Para cada vértice V, percorra as bordas do primeiro polígono:
• Encontre um "intervalo" de arestas voltadas para o vértice
• pegue o par externo de vértices que definem esse intervalo e remova todas as arestas no intervalo que os conecta
• Desenhe dois novos segmentos desses vértices externos para o novo vértice (do segundo polígono), certificando-se de que as novas arestas estejam voltadas para a direção correta.
• Prossiga para o próximo vértice do segundo polígono

Aqui está um diagrama que ilustra o processo para o primeiro vértice:

Um método mais rápido é encontrar a lista de arestas em cada polígono que não estão voltadas para o outro polígono, remover todo o resto e conectar os pontos finais das tiras de linhas restantes.

Talvez alguém possa concordar com alguns conselhos de subtração.