En geometría computacional , el problema de punto en polígono ( PIP ) pregunta si un punto dado en el plano se encuentra dentro, fuera o en el límite de un polígono . Es un caso especial de problemas de ubicación de puntos y encuentra aplicaciones en áreas que se ocupan del procesamiento de datos geométricos, como gráficos por computadora , visión por computadora , sistemas de información geográfica (GIS), planificación de movimiento y diseño asistido por computadora (CAD).
Una descripción temprana del problema en gráficos por computadora muestra dos enfoques comunes ( difusión de rayos y suma de ángulos) que se utilizaban ya en 1974. [1]
En un número de Ray Tracing News se puede encontrar un intento de los veteranos de los gráficos por ordenador de rastrear la historia del problema y algunos trucos para su solución . [2]
Una forma sencilla de encontrar si el punto está dentro o fuera de un polígono simple es probar cuántas veces un rayo , comenzando desde el punto y yendo en cualquier dirección fija, intersecta los bordes del polígono. Si el punto está en el exterior del polígono, el rayo cortará su borde un número par de veces. Si el punto está en el interior del polígono, cortará el borde un número impar de veces. El estado de un punto en el borde del polígono depende de los detalles del algoritmo de intersección de rayos.
Este algoritmo a veces también se conoce como algoritmo de números de cruce o algoritmo de regla par-impar , y se conocía ya en 1962. [3] El algoritmo se basa en una simple observación de que si un punto se mueve a lo largo de un rayo desde el infinito hasta el punto de sonda y si cruza el límite de un polígono, posiblemente varias veces, entonces alternativamente va de afuera hacia adentro, luego de adentro hacia afuera, etc. Como resultado, cada dos "cruces de frontera" el punto en movimiento sale afuera. Esta observación puede demostrarse matemáticamente utilizando el teorema de la curva de Jordan .
Si se implementa en una computadora con aritmética de precisión finita , los resultados pueden ser incorrectos si el punto se encuentra muy cerca de ese límite, debido a errores de redondeo. Para algunas aplicaciones, como videojuegos u otros productos de entretenimiento, esto no es una gran preocupación ya que a menudo prefieren la velocidad a la precisión. Sin embargo, para un programa de computadora formalmente correcto , uno tendría que introducir una tolerancia numérica ε y probar en línea si P (el punto) se encuentra dentro de ε de L (la línea), en cuyo caso el algoritmo debería detenerse e informar " P se encuentra ". muy cerca del límite."
La mayoría de las implementaciones del algoritmo de proyección de rayos verifican consecutivamente las intersecciones de un rayo con todos los lados del polígono por turno. En este caso se debe abordar el siguiente problema. Si el rayo pasa exactamente por un vértice de un polígono, entonces cortará 2 segmentos en sus puntos finales. Si bien está bien para el caso del vértice superior en el ejemplo o el vértice entre el cruce 4 y 5, el caso del vértice más a la derecha (en el ejemplo) requiere que cuentemos una intersección para que el algoritmo funcione correctamente. Un problema similar surge con los segmentos horizontales que caen sobre el rayo. El problema se resuelve de la siguiente manera: si el punto de intersección es un vértice de un lado del polígono probado, entonces la intersección cuenta sólo si el otro vértice del lado se encuentra debajo del rayo. Esto equivale efectivamente a considerar que los vértices del rayo se encuentran ligeramente por encima del rayo.
Una vez más, el caso del rayo que pasa por un vértice puede plantear problemas numéricos en aritmética de precisión finita : para dos lados adyacentes al mismo vértice, el cálculo sencillo de la intersección con un rayo puede no dar el vértice en ambos casos. Si el polígono se especifica por sus vértices, entonces este problema se elimina verificando las coordenadas y del rayo y los extremos del lado del polígono probado antes del cálculo real de la intersección. En otros casos, cuando los lados del polígono se calculan a partir de otros tipos de datos, se deben aplicar otros trucos para lograr la solidez numérica del algoritmo.
Otra técnica utilizada para comprobar si un punto está dentro de un polígono es calcular el número de devanado del punto dado con respecto al polígono. Si el número de devanado es distinto de cero, el punto se encuentra dentro del polígono. Este algoritmo a veces también se conoce como algoritmo de regla distinta de cero .
Una forma de calcular el número de devanado es sumar los ángulos subtendidos por cada lado del polígono. [4] Sin embargo, esto implica costosas funciones trigonométricas inversas , lo que generalmente hace que este algoritmo tenga un rendimiento ineficiente (más lento) en comparación con el algoritmo de proyección de rayos. Afortunadamente, no es necesario calcular estas funciones trigonométricas inversas. Dado que el resultado, la suma de todos los ángulos, puede sumar sólo 0 o (o múltiplos de ), es suficiente rastrear a través de qué cuadrantes se enrolla el polígono, [5] a medida que gira alrededor del punto de prueba, lo que hace que el devanado algoritmo numérico comparable en velocidad a contar los cruces de límites.
Dan Sunday desarrolló un algoritmo mejorado para calcular el número de devanados en 2001. [6] No utiliza ángulos en los cálculos, ni trigonometría, y funciona exactamente igual que los algoritmos de proyección de rayos descritos anteriormente. El algoritmo de Sunday funciona considerando un rayo horizontal infinito proyectado desde el punto que se está comprobando. Siempre que ese rayo cruza un borde del polígono, se utiliza el algoritmo de cruce de bordes de Juan Pineda (1988) [7] para determinar cómo afectará el cruce al número de devanados. Como lo describe Sunday, si el borde cruza el rayo que va "hacia arriba", el número de devanado aumenta; si cruza el rayo "hacia abajo", el número disminuye. El algoritmo de Sunday da la respuesta correcta para polígonos no simples, mientras que el algoritmo de cruce de límites falla en este caso. [6]
En SVG se utilizan métodos similares para definir una forma de rellenar con color varias formas (como rutas, polilíneas, polígonos, texto, etc.). [8] El algoritmo de llenado está influenciado por el atributo 'regla de llenado'. El valor puede ser cualquiera nonzeroo evenodd. Por ejemplo, en un pentagrama , hay un "agujero" central (fondo visible) con evenoddy ninguno con nonzeroatributo. [9]
Para polígonos simples , los algoritmos darán el mismo resultado. Sin embargo, para polígonos complejos , los algoritmos pueden dar resultados diferentes para puntos en las regiones donde el polígono se cruza, donde el polígono no tiene un interior y un exterior claramente definidos. Una solución que utiliza la regla par-impar es transformar polígonos (complejos) en polígonos más simples que sean equivalentes pares-impares antes de la verificación de la intersección. [10] Esto, sin embargo, es computacionalmente costoso. Es menos costoso utilizar el algoritmo numérico de bobinado rápido distinto de cero, que proporciona el resultado correcto incluso cuando el polígono se superpone.
El problema del punto en un polígono se puede considerar en la configuración general de consulta geométrica repetida : dado un solo polígono y una secuencia de puntos de consulta, encuentre rápidamente las respuestas para cada punto de consulta. Claramente, se puede utilizar cualquiera de los enfoques generales para la localización de puntos planos. Hay soluciones más simples disponibles para algunos polígonos especiales.
Son posibles algoritmos más simples para polígonos monótonos , polígonos en forma de estrella , polígonos convexos y triángulos .
El caso del triángulo se puede resolver fácilmente mediante el uso de un sistema de coordenadas baricéntrico , una ecuación paramétrica o un producto escalar . [11] El método del producto escalar se extiende naturalmente a cualquier polígono convexo.
