Encontre o número de ângulos internos de um polígono, maior que 180º

Question

Como posso encontrar o número de ângulos internos de um polígono, maior que 180º, tendo apenas os vértices do polígono?

Para cada vértice Quero sempre o ângulo interno, não a externa.

Graças do Brasil.

Answer 1

Você pode determinar o ângulo de dois vetores simplesmente tomando o produto escalar (produto de ponto). Uma propriedade útil é que se os vetores são ortogonais, seu produto escalar é zero; se o seu ângulo é obtuso, o produto é negativa, de outro modo positivo. Assim, os passos a tomar são:

• encontrar a primeira borda de V0 a V1 (como um vetor, você receber esse subtraindo as coordenadas) e rode-o em 90 graus para a esquerda (isto é apenas transformando (x y) para (-y x))
• encontrar a segunda borda de V1 a V2 (não rotacionada)
• levar o produto escalar (isto é apenas (x1 * x2) + (y1 * y2))
• se o produto escalar é negativo, é uma curva à direita, caso contrário, uma curva à esquerda
• próxima borda ...
• Se você percorrer os vértices sentido anti-horário, contar o número de voltas à direita, caso contrário, o número de voltas à esquerda
• para o último vértice, você tem que voltar para a primeira (ou seja, usar as bordas Vn para V0 e V0 a V1)

editar : Você pode encontrar se os vértices são ordenados sentido anti-horário ou horário, utilizando a seguinte fórmula para calcular a área do polígono:

     1  n-1
A = --- SUM( x(i)*y(i+1) - x(i+1)*y(i) )
     2  i=0

onde n é o número de vértices. x(n) e y(n) são os mesmos que x(0) e y(0) (para fechar o polígono).

Se for positivo, então os vértices são ordenados sentido anti-horário, caso contrário, no sentido horário.

editar : Quando você simplifica os passos de rotação e produto escalar, chega-se a fórmula para o produto cruzado bidimensional, x1*y2 - x2*y1. Isto simplifica os primeiros passos acima:

• encontrar o primeiro bordo de V0 a V1 (como um vector, subtraindo as coordenadas)
• dito para a segunda borda de V1 a V2
• tomar o ((x1 * y2) - (x2 * y1)) produto cruzado
• se o produto cruzado é positivo, é uma curva à esquerda

Sorry for a primeira abordagem complicado.

Answer 2

1. Encontre o convexo casco dos vértices.
2. Identificar os vértices que não mentira no casco convexo. Estes são os seus vértices candidatos com> 180 ângulos externos.
3. Para cada vértice investigar mais sobre o ângulo (não pode pensar em alguma forma agora, mas você pode estender este).

Answer 3

Eu estou assumindo que este é um polígono irregular, uma vez que seria muito difícil para um polígono regular para ter um maior ângulo interno de 180 graus.

Para cada vértice, você também precisa saber os dois vértices vizinhos. Você pode, então, transformar isso em um problema de trigonometria, onde você encontrar o ângulo do vértice principal para, digamos, o vértice esquerdo, e adicioná-lo ao ângulo do vértice principal para o vértice direito.

Por exemplo,

tan(angle_to_left) = (v.y-left.x)/(v.y-left.y)
tan(angle_to_right) = (v.y-right.x)/(v.y-right.y)

Em seguida, adicione os ângulos juntos.

Finalmente, para todos os ângulos que são maiores que 180, incrementar um contador. Depois de passar por todos os vértices, seu contador irá dizer-lhe como muitos ângulos internos são maiores do que 180.

Answer 4

O problema com a tangente é quando x == 0. Se você só conhece os vértices do polígono, você não sabe o suficiente a menos que seja um triângulo, uma vez que poderia ter qualquer tipo de conectividade.

Assumindo que você sabe a conectividade, então você vai precisar para calcular a ordem de enrolamento (ou seja, em que direção fazer os pontos ir ao redor do polígono?). Com a ordem de liquidação, você pode então tomar o produto cruzado de todos os pontos com seus pontos vizinhos e tomar o seno inverso da magnitude do que para obter o ângulo.

Answer 5

Encontrar o ângulo interior dos dois últimos vetores (como um exemplo), precisamos implementar esta equação para os últimos dois vetores do polígono:

= angleRadians Math.acos ((vx1 * VX2 + vy1 * VY2) / (Math.sqrt (vx1 * + VX1 vy1 * vy1) * Math.sqrt (VX2 * VX2 + VY2 * VY2)));

isso é usando o produto escalar dos vetores. Se você tiver dúvidas sobre isso, aqui está um tutorial

Mas isso não leva em conta o 'enrolamento direção', primeiro você deve obter o produto cruzado e, se o produto cruzado é positivo, foi uma curva à esquerda, se negativo - uma curva à direita (para o qual vamos compensar subtraindo ângulo (EXT) a partir de 360.

Eu incluí meu código JS aqui, como uma essência: https://gist.github.com/3741816 .

: D

Answer 6

Esta é uma pergunta relacionada com a geometria, não exatamente programação relacionados.

Se você tem os vértices, você pode apenas encontrar os ângulos internos de trigonometria, semelhante à forma como você encontrar os ângulos de um triângulo.

Usando três vértices adjacentes, imagine um triângulo e-los a encontrar os ângulos internos.

Por exemplo, olhar para o polígono:

Podemos construir um triângulo como: