Encuentra el número de ángulos internos de un polígono mayor que 180º.

Question

¿Cómo puedo encontrar la cantidad de ángulos internos de un polígono, más de 180º, con solo los vértices del polígono?

Para cada vértice quiero siempre el ángulo interno, no el externo.

Gracias desde Brasil.

Answer 1

Puedes determinar el ángulo de dos vectores simplemente tomando el producto escalar (producto escalar).Una propiedad útil es que si los vectores son ortogonales, su producto escalar es cero;si su ángulo es obtuso, el producto es negativo; en caso contrario, positivo.Entonces, los pasos a seguir son:

• encuentre el primer borde de V0 a V1 (como vector, se obtiene restando las coordenadas), luego gírelo 90 grados hacia la izquierda (esto solo es transformar (x y) a (-y x))
• encuentre el segundo borde de V1 a V2 (no girado)
• toma el producto escalar (esto es solo (x1 * x2) + (y1 * y2))
• si el producto escalar es negativo, es un giro a la derecha, en caso contrario es un giro a la izquierda
• siguiente borde...
• Si pasa por los vértices en el sentido contrario a las agujas del reloj, cuente el número de giros a la derecha; en caso contrario, el número de giros a la izquierda.
• para el último vértice, hay que volver al primero (es decir,use los bordes Vn a V0 y V0 a V1)

editar:Puedes saber si los vértices están ordenados en el sentido contrario a las agujas del reloj o en el sentido de las agujas del reloj usando la siguiente fórmula para calcular el área del polígono:

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

dónde n es el número de vértices. x(n) y y(n) son los mismos que x(0) y y(0) (para cerrar el polígono).

Si es positivo, entonces los vértices se ordenan en sentido antihorario; en caso contrario, en sentido horario.

editar:Cuando simplificas los pasos de rotación y producto escalar, llegas a la fórmula para el producto cruz bidimensional, x1*y2 - x2*y1.Esto simplifica los primeros pasos anteriores:

• encontrar la primera arista de V0 a V1 (como un vector, restando las coordenadas)
• dito para el segundo borde de V1 a V2
• toma el producto cruzado ((x1 * y2) - (x2 * y1))
• si el producto cruzado es positivo, es un giro a la izquierda

Perdón por el complicado primer enfoque.

Answer 2

1. convexa casco de los vértices.
2. Identificar los vértices que No se encuentran en el casco convexo. Estos son sus vértices candidatos con> 180 ángulos externos.
3. Para cada vértice investigar más a fondo sobre el ángulo (No se puede pensar en cualquier forma en este momento, pero se puede extender este).

Answer 3

Estoy asumiendo que este es un polígono irregular, ya que sería muy difícil para un polígono regular para tener un ángulo interno mayor de 180 grados.

Para cada vértice, que también tendría que conocer los dos vértices vecinos. A continuación, puede convertir esto en un problema de trigonometría, donde se encuentra el ángulo del vértice principal a, por ejemplo, el vértice izquierdo, y añadirlo al ángulo del vértice principal al vértice derecho.

Por ejemplo,

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

A continuación, añadir los ángulos juntos.

Finalmente, para todos los ángulos que son mayores que 180, incrementar un contador. Después de pasar por todos los vértices, su contador le dirá cuántos ángulos internos son mayores que 180.

Answer 4

El problema con tangente es cuando x == 0. Si sólo conoce los vértices del polígono, que no sabe lo suficiente a menos que sea un triángulo, ya que podría tener cualquier tipo de conectividad.

suponiendo que conoce la conectividad, a continuación, tendrá que calcular el orden de liquidación (es decir, en qué dirección van hacer los puntos alrededor del polígono?). Con la orden de disolución, a continuación, puede tomar el producto vectorial de todos los puntos con sus puntos vecinos y tomar el seno inverso de magnitud de que para obtener el ángulo.

Answer 5

Encontrar el ángulo interior de los dos últimos vectores (como un ejemplo), tenemos que aplicar esta ecuación para los dos últimos vectores del polígono:

angleRadians = Math.acos ((VX1 * vx2 + VY1 * VY2) / (Math.sqrt (VX1 * vx1 + VY1 * VY1) * Math.sqrt (vx2 * vx2 + VY2 * VY2)));

esto es utilizando el producto escalar de los vectores. Si tiene alguna pregunta sobre esto, aquí hay un tutorial

Pero eso no toma en cuenta la 'dirección de arrollamiento', primero debe obtener el producto cruz y, si el producto vectorial es positivo, fue un giro a la izquierda, si es negativo - un giro a la derecha (para lo cual compensar restando ángulo (ext) a partir de 360.

He incluido mi código JS aquí, como una esencia: https://gist.github.com/3741816 .

: D

Answer 6

Esta es una pregunta relacionada con la geometría, no exactamente programación relacionada.

Si usted tiene los vértices, sólo puede encontrar los ángulos internos de la trigonometría, de forma similar a cómo encontrar los ángulos de un triángulo.

Usando tres vértices adyacentes, imaginar un triángulo y a encontrar los ángulos internos.

Por ejemplo, mira el polígono:

Podemos construir un triángulo como: