El problema de si un punto pertenece a un polígono

En geometría computacional se conoce el problema de determinar si un punto pertenece a un polígono . Un polígono y un punto están dados en un plano . Se requiere para resolver la cuestión de si un punto pertenece a un polígono.

Un polígono puede ser convexo o no convexo. Se suele suponer que el polígono es simple, es decir, sin autointersecciones; pero el problema también se considera para polígonos no simples. En este último caso, diferentes formas de determinar si un punto pertenece a un polígono pueden conducir a resultados diferentes. Hay algoritmos sin preprocesamiento; y algoritmos con preprocesamiento, durante los cuales se crean unas estructuras de datos que les permiten responder más rápidamente a muchas consultas sobre si diferentes puntos pertenecen a un mismo polígono.

Método de trazado de rayos

Contabilización del número de intersecciones

Uno de los métodos estándar para determinar si un punto pertenece a un polígono simple arbitrario es el siguiente. Lancemos un rayo desde un punto dado en una dirección arbitraria (por ejemplo, en la dirección positiva del eje horizontal) y contemos cuántas veces el rayo cruza los bordes del polígono. Para hacer esto, es suficiente recorrer los bordes del polígono y determinar si el rayo interseca cada borde. Si el número de intersecciones es impar, se declara que el punto está dentro del polígono, si es par, entonces fuera. Esto se basa en la simple observación de que al moverse a lo largo del rayo, con cada cruce del límite, el punto se encuentra alternativamente dentro y fuera del polígono. El algoritmo se conoce con nombres como algoritmo de números cruzados (recuento) o regla par-impar .

El algoritmo tiene una dificultad en el caso degenerado cuando el rayo corta el vértice del polígono. Una forma de superarlo es asumir que dichos vértices de polígonos se encuentran una cantidad infinitesimal por encima (o por debajo) de la línea recta del rayo y, por lo tanto, en realidad no hay intersección. [1] Por lo tanto, la intersección de un rayo con un borde se cuenta si uno de los extremos del borde se encuentra estrictamente debajo del rayo, y el otro extremo está arriba o se encuentra sobre el rayo.

El algoritmo se ejecuta en tiempo O( N ) para un N - gon.

Contabilización del número de revoluciones

Considere el número de revoluciones que hace el límite orientado del polígono alrededor de un punto P dado . En topología algebraica, este número se llama índice del punto con respecto a la curva . [2] Se puede calcular de la siguiente manera. Como antes, disparemos un rayo desde P en una dirección arbitraria y consideremos las aristas que intersecta. Asignamos un número de +1 o -1 a cada intersección, dependiendo de cómo la arista interseca el rayo: en el sentido de las agujas del reloj (de izquierda a derecha) o en el sentido contrario a las agujas del reloj (de derecha a izquierda). Estos dos casos se pueden distinguir por el signo del producto escalar entre el vector de dirección del borde y la normal al vector de dirección del rayo. [3] La suma de los valores obtenidos es el índice del punto relativo a la curva . La suma será positiva o negativa, dependiendo de la orientación del borde. Si no es igual a cero, supondremos que el punto se encuentra dentro del polígono; de lo contrario, afuera.

Tal algoritmo se conoce como la regla de devanado distinta de cero . [3]

Para polígonos simples, este método funciona de la misma manera que el método basado en contar el número de intersecciones. La diferencia entre ellos se hace evidente cuando se consideran polígonos con un límite de autointersección.

Método de suma de ángulos

Se puede determinar que el punto P está dentro de un polígono con vértices V 0 , V 1 , ..., V n = V 0 calculando la suma:

donde  es el ángulo (en radianes y con signo) entre los rayos PV i − 1 y PV i , es decir:

Se puede probar que esta suma no es más que el número de vueltas del punto P con respecto al límite del polígono, hasta un factor constante . Por lo tanto, podemos suponer que el punto se encuentra fuera del polígono si la suma es igual a cero (o lo suficientemente cerca de él, si se usa la aritmética aproximada). Sin embargo, este método es muy poco práctico, ya que requiere el cálculo de costosas operaciones para cada arista (funciones trigonométricas inversas, raíces cuadradas), e incluso ha sido llamado el "peor algoritmo del mundo" para este problema [1] .

K. Weiler propuso una versión práctica de este método, evitando costosas operaciones y cálculos aproximados. [4] Se demostró que la suma de los ángulos puede calcularse utilizando únicamente la operación de clasificar un punto poligonal en cuadrantes con respecto al punto P . El algoritmo de Weiler y algunas de sus mejoras se describen en [5] .

Algoritmos con preprocesamiento

Polígonos convexos y en estrella

Se puede determinar si un punto pertenece a un N - gon convexo o estrella mediante la búsqueda binaria en el tiempo O (log N ), la memoria O ( N ) y el tiempo de preprocesamiento O ( N ). [6]

Polígono arbitrario

El problema de si un punto pertenece a un polígono simple arbitrario puede considerarse como un caso especial del problema de localizar un punto en una subdivisión plana. Para un N -gon, este problema puede resolverse en tiempo O(log 2 N ) usando memoria O( N ) y tiempo de preprocesamiento O( N log N ) . [7]

Notas

  1. ↑ 1 2Eric Haines. Point in Polygon Strategies Archivado el 25 de septiembre de 2011 en Wayback Machine .
  2. ↑ Se puede traducir al ruso como "índice de curva relativo a un punto", "número de torsión", "número de bobinado", "número de tornillo" y similares.
  3. ↑ 1 2 Foley JD, et al. Gráficos por computadora: principios y práctica. AddisonWesley. 1990. Pág. 965.
  4. ↑ K. Weiler. Un punto de ángulo incremental en la prueba del polígono, en: P. Heckbert (Ed.), Graphic Gems IV, Academic Press, Boston, MA, 1994, pp. 16-23.
  5. ↑ Hormann K., Agathos A. El problema del punto en el polígono para polígonos arbitrarios   // Comput . Geom. Aplicación de la teoría. - 2001. - vol. 20 _ - P. 131-144 .
  6. ↑ Preparata, Sheimos. Página 60-61.
  7. ↑ Preparata, Sheimos. Página 74. Teorema 2.6.

Literatura

Enlaces