Punto en polígono

En geometría computacional, el problema del punto en un 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.

En un número de Ray Tracing News se puede encontrar un intento de los veteranos en gráficos por computadora de rastrear la historia del problema y algunos trucos para su solución.

Algoritmo de emisión de rayos

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 cruzados o algoritmo de regla par-impar, y se conocía ya en 1962. El algoritmo se basa en un 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, después de cada dos "cruces fronterizos" el punto en movimiento sale al exterior. Esta observación puede demostrarse matemáticamente utilizando el teorema de la curva de Jordan.

Precisión limitada

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 en del rayo se encuentran ligeramente encima del rayo.

Una vez más, el caso del rayo que pasa a través de 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.

Algoritmo del número de bobinado

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 manera de calcular el número de enrollamiento es resumir los ángulos subtended por cada lado del polígono. Sin embargo, esto implica funciones trigonométricas costosas inversas, lo que generalmente hace que este algoritmo de rendimiento ineficiente (más bajo) en comparación con el algoritmo de fundición de rayos. Por suerte, estas funciones trigonométricas inversas no necesitan ser calculadas. Desde el resultado, la suma de todos los ángulos, puede añadir hasta 0 o ${displaystyle 2pi}$ (o múltiples de ${displaystyle 2pi}$) sólo, es suficiente para rastrear a través de qué cuadrantes los vientos del polígono, ya que gira alrededor del punto de prueba, lo que hace que el número de viento algoritmo 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. 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) para determinar cómo el cruce afectará el 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.

Implementaciones

SVG

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.). El algoritmo de llenado está influenciado por la 'regla de llenado' atributo. El valor puede ser nonzero o evenodd. Por ejemplo, en una superficie pentagonal regular no convexa, hay un "agujero" (fondo visible) con evenodd, y ninguno con < código class="mw-highlight mw-highlight-lang-text mw-content-ltr" id="" style="" dir="ltr">nonzero atributo.

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. Sin embargo, esto 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.

Consultas de punto en polígono

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.

Casos 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. El método del producto escalar se extiende naturalmente a cualquier polígono convexo.