Como determinar uma diagonal é dentro ou fora de um polígono côncavo?

Question

A diagonal (uma diagonal é um segmento que liga os vértices não adjacentes) de um côncava (não-convexo) polígono pode ser completamente dentro ou para fora do polígono (ou pode intersectam com as bordas do polígono). Como determinar se ele está completamente no polígono? ( um método sem teste de ponto no polígono ).

Answer 1

Se a diagonal tem, pelo menos, uma intersecção com as arestas, que é parcialmente dentro e parcialmente fora do polígono, contudo, se a diagonal não tem intersecção com eles, existem apenas dois estados: é compeletely em ou completamente fora do polígono.

Para determinar se ele está dentro ou fora do polígono:

vértices do polígono Suponha que são classificadas anti-horário. Considere uma das extremidades da diagonal que se situa sobre o vértice chamado P [i] (a outra extremidade é p [j]). Em seguida, faça três vetores cujos primeiros pontos são p [i]:

V1: p [i + 1] - p [i]

V2: p [i-1] - p [i]

V3: p [j] - p [i]

A diagonal é completamente no polígono se e somente se V3 é entre V1 e V2 quando se deslocar horário de V1 a V2.

Como determinar se V3 é entre V1 e V2 quando vamos de V1 a V2 anti-horário? ir para aqui .

Eu escrevi um programa usando este método e funciona de forma eficaz.

Answer 2

Como determinar se ele está completamente no polígono?

Se você quiser determinar se uma diagonal nunca deixa de fronteira do polígono, apenas determinar se é ou não cruza todas as linhas entre dois vértices adjacentes.

• Se isso acontecer, é parcialmente dentro e parcialmente fora do polígono.

• Se não, ou é completamente dentro ou completamente fora do polígono. A partir daí, o método mais simples é usar o ponto no polígono em qualquer ponto da diagonal, mas se você não quiser fazer isso, use o enrolamento algoritmo .

Answer 3

Eu acredito que a resposta de John perde um caso importante: quando a diagonal é completamente fora do polígono a partir do get-go. Imagine fazer a "ponte" diagonal as duas torres do seu "u" polígono em forma.

Eu tive que resolver isso há vários anos, então por favor, perdoe se minha lembrança é um pouco irregular.

A forma I resolveu este era para executar testes de linha de intersecção da diagonal contra cada borda do polígono. Você então tem dois casos possíveis: ou tinham pelo menos um cruzamento, ou você não tinha cruzamentos. Se você receber quaisquer cruzamentos, a diagonal não é dentro do polígono.

Se você não obter quaisquer cruzamentos, você precisa determinar se a diagonal é completamente dentro ou completamente fora do polígono. Digamos que a diagonal está se juntando p [i] para p [j], que i

Uma vez feito isso, o ângulo 2D da diagonal será positivo se a diagonal está fora do polígono, ou negativo, se é dentro do polígono.

Answer 4

No que diz respeito à verificação de cruzamentos entre segmentos de linha (que é o primeiro passo que você provavelmente tem que fazer), eu achei as explicações sobre SoftSurfer para ser útil. Você teria que verificar se há um cruzamento entre a diagonal e qualquer uma das bordas do polígono. Se você estiver usando MATLAB, você deve ser capaz de encontrar uma maneira eficiente para verificar cruzamentos para todas as arestas em simultâneo com as operações da matriz e do vetor (eu lidei com computação pontos de intersecção desta forma para intersecções raio-triângulo ).

Answer 5

A resposta de John está no local:

Se você quiser determinar se uma diagonal nunca deixa o polígono de limite, apenas determinar se é ou não cruza todas as linhas entre dois vértices adjacentes. Se assim for, resta o polígono.

Uma maneira eficiente de fazer esta verificação é executar o algoritmo sweepline Bentley-Ottman sobre os dados. É fácil de implementar, mas difícil de fazer estável numérica. Se você tem menos de ... digamos ... 20 bordas das polígonos uma pesquisa de força bruta provavelmente será mais rápido.