Como cruzar dois polígonos?

Isso parece não-trivial (ele é perguntado bastante em vários fóruns), mas eu absolutamente preciso disso como um bloco de construção para um algoritmo mais complexo.

Entrada : 2 polígonos (A e B) em 2D, dados como uma lista de arestas [(x0, y0, x1, y2), ...] cada. Os pontos são representados por pares de s double . Eu não sei se eles são dados no sentido horário, anti-horário ou em qualquer direção. Eu sei que eles não são necessariamente convexos.

Saída : 3 polígonos representando A, B e o polígono de interseção AB. Qualquer um dos quais pode ser um polígono vazio (?), Por exemplo, null .

Dica para otimização : esses polígonos representam os limites da sala e do piso. Assim, o limite da sala normalmente se cruzará totalmente com o limite do piso, a menos que ele pertença a outro andar no mesmo plano (argh!).

Eu meio que espero que alguém já tenha feito isso em c # e me deixe usar sua estratégia / código, já que o que eu encontrei até agora sobre esse problema é bastante assustador.

EDIT : Assim, parece que eu não sou inteiramente de frango por feiling fraco na perspectiva de fazer isso. Gostaria de reafirmar a saída desejada aqui, pois esse é um caso especial e pode tornar a computação mais simples:

Saída : Primeiro polígono menos todos os bits de interseção, polígonos de interseção (plural é ok). Eu não estou realmente interessado no segundo polígono, apenas na sua interseção com o primeiro.

EDIT2 : Atualmente, estou usando a biblioteca GPC (General Polygon Clipper) que facilita muito isso!

O que eu acho que você deveria fazer

Não tente fazer isso sozinho se puder ajudá-lo. Em vez disso, use um dos muitos algoritmos de interseção de polígonos disponíveis que já existem.

Eu estava considerando fortemente a seguinte base de código sobre a força de seu código de demonstração e o fato de que eles mencionaram o manuseio da maioria / todos os casos estranhos. Você precisaria doar uma quantia (de você / a escolha de sua empresa) se você a usar comercialmente, mas vale a pena obter uma versão robusta desse tipo de código.

http://www.cs.man.ac.uk/~toby/gpc/

O que eu realmente fiz foi usar um algoritmo de intersecção de polígonos que faz parte das bibliotecas Java2D. Você pode encontrar algo similar nas próprias bibliotecas C # do MS para usar.

Existem outras opções por aí também; procure por “clipper de polígonos” ou “clipping de polígono”, pois os mesmos algoritmos básicos que manipulam a interseção de polígonos também tendem a ser utilizáveis ​​para os casos gerais de recorte.

Uma vez que você realmente tem uma biblioteca de recortes de polígonos, você só precisa subtrair o polígono B do polígono A para obter sua primeira saída e cruzar os polígonos A e B para obter sua segunda saída.

Como rolar o seu próprio, para o irremediavelmente masoquista

Quando eu estava pensando em fazer o meu próprio, eu encontrei o algoritmo Weiler-Atherton para ter o maior potencial para o corte geral de polígonos. Eu usei o seguinte como referência:

http://cs1.bradley.edu/public/jcm/weileratherton.html

http://en.wikipedia.org/wiki/Weiler-Atherton

Os detalhes, como dizem, são muito densos para include aqui, mas não tenho dúvidas de que você poderá encontrar referências em Weiler-Atherton nos próximos anos. Essencialmente, você divide todos os pontos naqueles que estão entrando no polígono final ou saindo do polígono final, então você forma um gráfico de todos os pontos e, em seguida, percorre o gráfico nas direções apropriadas para extrair todas as peças do polígono que você quer. Ao alterar a maneira de definir e tratar os polígonos “entrando” e “saindo”, você pode obter várias interseções de polígonos possíveis (AND, OR, XOR, etc.).

Na verdade, é bastante implementável, mas como acontece com qualquer código de geometry computacional, o diabo está nas degenerações.

A biblioteca FastGEO da Arash Partow contém implementações de muitos algoritmos interessantes em geometry computacional. O cruzamento de polígonos é um deles. Está escrito em Pascal, mas está apenas implementando a matemática, então é bem legível. Note que você certamente precisará pré-processar suas bordas um pouco, para colocá-las no sentido horário ou anti-horário.

ETA: Mas, realmente, a melhor maneira de fazer isso é não fazer isso . Encontre outra maneira de abordar seu problema que não envolva interseções arbitrárias de polígonos.

Se você estiver programando no .NET Framework, talvez queira dar uma olhada na class SqlGeometry disponível em assemblies .NET fornecidos como tipos CLR do Sistema Microsoft SQL Server.

A class SqlGeometry fornece o método STIntersection

 SqlGeometry g1 = SqlGeometry.Parse("POLYGON ((...))"); SqlGeometry g2 = SqlGeometry.Parse("POLYGON ((...))"); SqlGeometry intersection = g1.STIntersection(g2); 

Você também pode querer dar uma olhada no NetTopologySuite ou até mesmo tentar importá-lo para o Sql Server 2008 e suas ferramentas espaciais.

Um polígono é totalmente descrito por uma lista ordenada de pontos (P1, P2, …, Pn). As arestas são (P1 – P2), (P2 – P3), …, (Pn – P1). Se você tiver dois polígonos A e B que se sobrepõem, haverá um ponto A (da lista em pontos que descrevem o polígono A) que fica dentro da área cercada pelo polígono B ou vice-versa (um ponto B está em A). Se nenhum desses pontos for encontrado, os polígonos não se sobrepõem. Se tal ponto for encontrado (ie Ai), verifique os pontos adjacentes do polígono A (i-1) e A (i + 1). Repita até encontrar um ponto fora da área ou todos os pontos estão marcados (então o primeiro polígono fica completamente dentro do segundo polígono). Se você encontrou um ponto fora, você pode calcular o ponto de travessia. Encontre a borda correspondente do polígono B e siga-a com papéis ressersed = agora verifique se os pontos do polígono B estão dentro do polígono A. Dessa forma, você pode criar uma lista de pontos que descrevem o polígono sobreposto. Se necessário, você deve verificar se os polígonos são idênticos (P1, P2, P3) === (P2, P3, P1).

Esta é apenas uma ideia e talvez haja formas melhores. Se você encontrar uma solução funcional e testada, eu recomendo que você a use …

narozed

Tente usar ferramentas GIS para isso, como ArcObjects, TopologySuite, GEOS, OGR, etc. Não tenho certeza se todas essas distribuições são disponíveis para .net, mas todas fazem o mesmo.

Clipper é uma biblioteca de clipping de polígonos freeware de código aberto (escrita em Delphi e C ++) que faz exatamente o que você está perguntando – http://sourceforge.net/projects/polyclipping/

Nos meus testes, o Clipper é significativamente mais rápido e menos propenso a erros do que o GPC (veja comparações mais detalhadas aqui – http://www.angusj.com/delphi/clipper.php#features ). Além disso, embora exista código-fonte para o Delphi e o C ++, a biblioteca do Clipper também inclui uma DLL compilada para tornar muito fácil o uso das funções de recorte em outros idiomas (Windows) também.

Este trabalho acadêmico explica como fazer isso.

Se você ousar dar uma olhada no código GPL C ++ de outras pessoas, você pode ver como eles fazem isso no Inkscape:

http://bazaar.launchpad.net/~inkscape.dev/inkscape/trunk/view/head:/src/2geom/shape.cpp (linha 126)