Búsqueda de orientación
Dentro de una secuencia de comandos, el polígono estará disponible como un conjunto de anillos-un anillo exterior y cero o más anillos interiores-con cada anillo representa por un cíclicamente ordenó tupla de vectores (v[0], v1, ..., v[m-1], v[m] = v[0]). Cada vector da las coordenadas de un vértice (no hay dos sucesivos vértices coincidentes). A partir de esto es sencillo, como otros han señalado, para obtener los vectores normales (es decir, los vectores perpendiculares al borde direcciones):
n[i] = t(v[i+1] - v[i]).
La "t" de la operación a la que gira un vector de 90 grados hacia la izquierda:
t( (x, y) ) = (y, -x).
Sólo las direcciones de estos vectores normales de la materia, por lo reescala a tener unidad de longitud: un vector (x, y) escala a (x/s, s/s), donde s = Sqrt(x^2 + y^2) (que es la longitud de su borde correspondiente). A partir de ahora, vamos a suponer que esto se ha hecho. Escribir las componentes de la resultante de la unidad de vectores normales como
n[i] = (u[i], v[i]), i = 0, 1, ..., m-1.
Discriminar fuera desde el interior
Como comentario, esto deja una direccional de la ambigüedad: debemos ser el uso de n[i] o -n[i]? Que uno de los puntos hacia el exterior? Esta pregunta es equivalente a encontrar el grado de Gauss mapa. Para calcular esto, usted necesita a la suma de los ángulos por los que la dirección de las normales de cambiar a medida que la marcha alrededor de un anillo. Debido a que los vectores normales tienen unidad de longitud, el coseno del ángulo entre dos sucesivas, de bordes
Cos(q_i) = n[i] . n[i+1] = u[i]*u[i+1] + v[i]*v[i+1], i = 0, 1, ..., m-1.
(Definir n[m] = n[0].)
El seno del ángulo entre dos sucesivas, de bordes
El pecado(q_i) = n[i] . t(n[i+1]) = u[i]*v[i+1] - v[i]*u[i+1].
(Tenga en cuenta que estos cálculos requieren sólo sumas, diferencias y productos hasta el momento.) La aplicación de los principales inversa de la función tangente (ATan2) para cualquier (coseno, seno) par da el ángulo q_i entre -180 y 180 grados. Sumando los ángulos para i = 0, 1, ..., n-1 produce (hasta el punto flotante de error) el total de la curvatura del anillo, que debe ser un múltiplo de 360 grados; para un cierre no-auto-intersección del anillo es wil +360 o -360. En el primer caso, el grado es 1 y en el segundo caso, el grado es -1. Las normales son todo exterior orientado a cuando el grado de que el anillo exterior es de +1 y los grados de los anillos interiores son de -1. Re-orientar el anillo por anillo, según sea necesario, de acuerdo a esta regla. Es decir, si el grado de cualquier anillo es el opuesto de lo que es necesario, anular todas las normales para que el anillo. Ahora puedes continuar con su insolación cálculos.