Como determino se um polígono contém completamente outro?

9

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:

polígonos de exemplo

user960567
fonte
Não posso dar uma resposta detalhada agora (talvez faça isso mais tarde), mas você deve dar uma olhada em uma implementação do teorema do eixo de separação para detecção de colisão. O algoritmo pode ser ligeiramente modificado para verificar facilmente o que você deseja. por exemplo, codezealot.org/archives/55
TravisG 13/06
11
Você não sabe exatamente o que entende de um polígono dentro de um polígono. E se todos os pontos do polígono menor estiverem no maior, mas cada um deles tiver um lado em uma linha, eles estão um no outro? i47.tinypic.com/4i0sgg.jpg
Speedy González
@speedyGonzales, isso também é chamado por dentro.
user960567

Respostas:

5

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):

  bool isInside = true;
  for each (Point p in innerPoly)
  {
    if (!PointInsidePolygon(p, outerPoly))
    {
      isInside = false; // at least one point of the innerPoly is outside the outerPoly
      break;
    }
  }
  if (!isInside) return false;
  // COMPULSORY EDGE INTERSECTION CHECK
  for each (innerEdge in innerPoly)
    for each (outerEdge in outerPoly)
    {
      if (EdgesIntersect(innerEdge, outerEdge))
      {
        isInside = false;
        break;
      }
    }

  return isInside;

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 se innerEdgefor um subconjunto (geometricamente) do outerEdge. 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 da isInsidevariável

Comentá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.

teodron
fonte
11
Isso retornará falsos positivos quando o polígono externo for côncavo.
21712 Sam Sami Hocevar
2
Curiosamente, embora os teodron e knight666 estejam errados individualmente, quando combinados, eles devem dar a resposta certa. Se todos os pontos de um polígono estiverem dentro de outro e se suas linhas não se cruzarem, o primeiro polígono estará completamente dentro do outro.
precisa
É verdade que ele retorna falsos positivos, e também precisa levar em consideração as interseções das arestas.
Teodron #
Esta parece ser a resposta correta. Eu acho que não precisava verificar a segunda condição do loop.
user960567
Isso não funciona para interseções de pontos de extremidade ou se as arestas se sobrepuserem.
Brandon Kohn
2

Tente fazer uma interseção de linha com cada linha vermelha. No pseudocódigo:

// loop over polygons
for (int i = 0; i < m_PolygonCount; i++)
{
    bool contained = false;

    for (int j = 0; j < m_Polygon[i].GetLineCount(); j++)
    {
        for (int k = 0; k < m_PolygonContainer.GetLineCount(); k++)
        {
            // if a line of the container polygon intersects with a line of the polygon
            // we know it's not fully contained
            if (m_PolygonContainer.GetLine(k).Intersects(m_Polygon[i].GetLine(j)))
            {
                contained = false;
                break;
            }
        }

        // it only takes one intersection to invalidate the polygon
        if (!contained) { break; }
    }

    // here contained is true if the polygon is fully inside the container
    // and false if it's not
}

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:

  • Renderize o polígono do contêiner em um buffer de pixel com uma cor branca.
  • Renderize um polígono filho em um buffer de pixel diferente com uma cor branca.
  • Mascarar o buffer do contêiner sobre o buffer do polígono com uma máscara XOR.
  • Conte o número de pixels brancos; se for maior que 0, o polígono filho não será totalmente contido pelo contêiner.

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ê.

knight666
fonte
11
As interseções de linha não serão suficientes para detectar polígonos totalmente contidos.
Kylotan
11
Pergunta: se os polígonos estiverem completamente separados, nenhuma aresta se cruzará. Funcionará neste caso? A segunda abordagem baseada em gráficos deve funcionar de fato!
Teodron #