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 tratan con el 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 de computadora muestra dos enfoques comunes ( lanzamiento de rayos y suma de ángulos) en uso ya en 1974. [1]
Un intento de los veteranos de los gráficos por ordenador de rastrear la historia del problema y algunos trucos para su solución se puede encontrar en un número de Ray Tracing News . [2]
Una forma sencilla de averiguar si el punto está dentro o fuera de un polígono simple es comprobar cuántas veces un rayo , que parte del punto y sigue una dirección fija, interseca los bordes del polígono. Si el punto está fuera del polígono, el rayo intersecará su borde un número par de veces. Si el punto está dentro del polígono, intersecará 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 también se conoce a veces como algoritmo de número 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 va alternativamente desde el exterior hacia el interior, luego desde el interior hacia el exterior, etc. Como resultado, después de cada dos "cruces de frontera", el punto en movimiento va hacia el exterior. 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 los videojuegos u otros productos de entretenimiento, esto no es una gran preocupación ya que a menudo priorizan la velocidad sobre 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 comprueban consecutivamente las intersecciones de un rayo con todos los lados del polígono uno por uno. En este caso, se debe abordar el siguiente problema. Si el rayo pasa exactamente por un vértice de un polígono, entonces intersectará 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 de 4 y 5, el caso del vértice más a la derecha (en el ejemplo) requiere que contemos una intersección para que el algoritmo funcione correctamente. Surge un problema similar 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 solo si el otro vértice del lado se encuentra debajo del rayo. Esto es efectivamente equivalente 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 directo 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 comprobando 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 la robustez 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 vueltas del punto dado con respecto al polígono. Si el número de vueltas no es cero, el punto se encuentra dentro del polígono. Este algoritmo a veces también se conoce como el algoritmo de la regla de no cero .
Para comprobar si un punto dado se encuentra dentro o fuera de un polígono:
Una forma de calcular el número de vueltas es sumar los ángulos subtendidos por cada lado del polígono. [5] Sin embargo, esto implica costosas funciones trigonométricas inversas , lo que generalmente hace que este algoritmo sea ineficiente en términos de rendimiento (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 0 o (o múltiplos de ) solamente, es suficiente rastrear a través de qué cuadrantes se enrolla el polígono, [6] mientras gira alrededor del punto de prueba, lo que hace que el algoritmo del número de vueltas sea comparable en velocidad al conteo de los cruces de límites.
En 2001, Dan Sunday desarrolló un algoritmo mejorado para calcular el número de vueltas. [7] 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 una arista del polígono, se utiliza el algoritmo de cruce de aristas de Juan Pineda (1988) [8] para determinar cómo afectará el cruce al número de vueltas. Como lo describe Sunday, si la arista cruza el rayo que va "hacia arriba", el número de vueltas se incrementa; si cruza el rayo "hacia abajo", el número se decrementa. 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. [7]
En SVG se utilizan métodos similares para definir una forma de rellenar con color diversas formas (como trazados, polilíneas, polígonos, textos, etc.). [9] El algoritmo de relleno está influenciado por el atributo 'fill-rule'. El valor puede ser nonzeroo evenodd. Por ejemplo, en un pentagrama , hay un "agujero" central (fondo visible) con evenodd, y ninguno con nonzeroel atributo . [10]
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 interseca a sí mismo, donde el polígono no tiene un interior y 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 a pares-impares antes de la verificación de intersección. [11] Sin embargo, esto es computacionalmente costoso. Es menos costoso utilizar el algoritmo de número de bobinado rápido distinto de cero, que da el resultado correcto incluso cuando el polígono se superpone a sí mismo.
El problema del punto en un polígono puede considerarse en el contexto general de una consulta geométrica repetida : dado un solo polígono y una secuencia de puntos de consulta, encontrar rápidamente las respuestas para cada punto de consulta. Claramente, se puede utilizar cualquiera de los enfoques generales para la ubicación de puntos planos . Existen soluciones más simples 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 . [12] El método del producto escalar se extiende naturalmente a cualquier polígono convexo.
