Calcular a união de duas formas arbitrárias

Question

Estou trabalhando em um aplicativo, preciso combinar duas formas arbitrárias sobrepostas desenhadas pelo usuário.Esta seria uma operação da União nas duas formas.A forma resultante seria a silhueta das duas formas sobrepostas.

As formas são armazenadas como uma sequência de pontos no sentido horário.

Idealmente, eu gostaria de um algoritmo que pegasse duas matrizes de pontos (x,y) e retornasse uma única matriz da forma resultante.

Eu tenho lido a Wikipedia em Operações booleanas em polígonos que menciona o Algoritmo de linha de varredura mas não consigo fazer a ligação entre isso e meu objetivo, infelizmente não sou matemático.

Estou desenvolvendo o aplicativo em ActionScript 3, mas estou familiarizado com C#, Java e posso escolher C e C++.

Answer 1

A implementação de operações booleanas corretamente não é trivial; Felizmente, existem bibliotecas que já implementam essa funcionalidade.

Que linguagem você está usando? Se for C ++, dê uma olhada CGAL, a biblioteca de algoritmos de geometria computacional.

Answer 2

Dado duas listas de pontos (A e B)
- [1] Para cada linha em a faz isso cruzando uma linha em B
-.- [2] Se não (mais) linhas se cruzarem, não há sobreposição
-.- [3] se uma linha em (a) cruza uma linha em B, então
-.-.- [4] Adicione o ponto de interseção na saída
-.-.- [5] faz a próxima linha de um intersect b
-.-.
-.-.-.- [7] se for o

Veja também Ponto de interseção de duas linhas. Eu não vou escrever o código, desculpe :)

Answer 3

Veja também GPC.

Answer 4

Gostaria Este algoritmo Trabalho para você?

Answer 5

Que tal:

1. Escolha o ponto mais à esquerda das duas formas.Chame essa Forma A e torne-a a forma atual.
2. Gire no sentido horário ao longo da forma atual até o próximo ponto e verifique se uma ou mais linhas se cruzam.
   • Se alguma linha se cruzar, encontre o primeiro ponto de interseção e adicione-o à sua nova forma.Mude para o enrolamento ao longo da outra forma.
   • Se nenhuma linha se cruzar, passe para o próximo ponto na forma A e adicione-o como o ponto na sua nova forma.Continue enrolando ao longo da forma atual.
3. Repita a Etapa 2.

Acho que se você continuar seguindo qualquer forma atual, procurando interseções, isso deve fazer o que você deseja.Acho que isso também deve funcionar com formas côncavas...

Tenho certeza de que há muitas otimizações que você pode adicionar depois de ter o básico funcionando.

Answer 6

Parece também haver uma API JavaScript:

https://github.com/bjnharrtell/jsts/

que parece implementar o padrão JTS e tem várias implementações diferentes:

http://tsusiToftware.net/jts/jts-links.html#ports

Todos eles devem ser capazes de realizar união etc:

http://tsusiToftware.net/jts/jtsuser/contents.html

Mas CSG.js é o projeto mais impressionante da IMO

https://github.com/evanw/csg.js