Eu tenho 2 polígonos. Eu sei as coordenadas de vértice de ambos os polígonos. Qual é a melhor maneira de verificar se um está completamente dentro do outro? Por exemplo, o algoritmo deve reconhecer apenas o trapézio preto abaixo como contido:
collision-detection
vector
geometry
user960567
fonte
fonte
Respostas:
Existem muitos trechos de código-fonte para um método que executa um teste para " ponto dentro do polígono ". O princípio vem do teorema da curva de Jordan para polígonos ( http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Octavian/compgeom.html ).
A maneira ingênua seria: tendo esse método, chame-o
PointInsidePolygon(Point p, Polygon poly)
:Teoricamente, ele não deve perder nenhum cenário para seus polígonos, mas não é a solução ideal.
Observações do caso "Edge"
PointInsidePolygon(..)
deve retornar true se o ponto estiver na borda do polígono (está em uma aresta ou é um vértice)EdgesIntersect(..)
deve retornar false seinnerEdge
for um subconjunto (geometricamente) doouterEdge
. Nesse caso, as arestas obviamente se cruzam, mas, para o propósito do algoritmo, precisamos indicar que a interseção não está quebrando a semântica por trás daisInside
variávelComentários gerais :
sem verificações de interseção de arestas x arestas, conforme indicado nos comentários, a abordagem pode retornar falsos positivos para alguns polígonos côncavos (por exemplo, um quad e um retângulo em forma de V - o retângulo pode ter todos os seus vértices dentro da forma de V, mas interceptá-lo , tendo pelo menos algumas áreas externas).
depois de verificar se pelo menos um dos vértices do polígono interno está dentro do externo e se não houver arestas que se cruzam, significa que a condição procurada é satisfeita.
fonte
Tente fazer uma interseção de linha com cada linha vermelha. No pseudocódigo:
No entanto, como você pode ver, essa solução ficará mais lenta à medida que você adiciona mais polígonos para verificar. Uma solução diferente pode ser:
Essa solução é muito rápida, mas depende da sua implementação (e do que você deseja fazer com o resultado da sua verificação) que solução funciona melhor para você.
fonte