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 del punto de localización problemas y aplicaciones encuentra en áreas que tienen que ver con el procesamiento de los datos geométricos, tales como gráficos por ordenador , la visión por computador , sistemas de información geográfica (GIS), planificación de movimientos , y CAD .
Una descripción temprana del problema en gráficos por computadora muestra dos enfoques comunes (proyección de rayos y suma de ángulos) en uso ya en 1974. [1]
Un intento de los veteranos de los gráficos por computadora para rastrear la historia del problema y algunos trucos para su solución se pueden encontrar en un número de Ray Tracing News . [2]
Algoritmo de lanzamiento de rayos
Una forma sencilla de averiguar 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, interseca los bordes del polígono. Si el punto está en el exterior del polígono, el rayo intersecará su borde un número par de veces. Si el punto está en el interior 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 es a veces también conocido como el algoritmo número cruce o la regla par-impar algoritmo , y era conocido 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 la punto de prueba y si cruza el límite de un polígono, posiblemente varias veces, entonces va alternativamente de afuera hacia adentro, luego de adentro hacia afuera, etc. Como resultado, después de cada dos "cruces fronterizos", 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. Normalmente, esto no es una preocupación, ya que la velocidad es mucho más importante que la precisión total en la mayoría de las aplicaciones de gráficos por computadora. [ dudoso ] 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) está dentro de ε de L (la línea), en cuyo caso el algoritmo debería detenerse e informe " 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 solucionar el siguiente problema. Si el rayo pasa exactamente a través de un vértice de un polígono, entonces intersecará 2 segmentos en sus extremos. Si bien está bien para el caso del vértice más alto 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 contemos 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 de polígono probado, entonces la intersección cuenta solo si el segundo vértice del lado se encuentra debajo del rayo. Esto es efectivamente equivalente a considerar vértices en el rayo como la mentira ligeramente por encima de la ray.
Una vez más, el caso del rayo que atraviesa 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 la robustez numérica del algoritmo.
Algoritmo de número de bobinado
Otro algoritmo es calcular el número de bobinado 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 reglas distintas 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 sea más lento que el algoritmo de proyección de rayos. Afortunadamente, estas funciones trigonométricas inversas no necesitan calcularse. 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 los vientos del polígono, [5] a medida que gira alrededor del punto de prueba, lo que hace que el algoritmo del número de devanado sea comparable en velocidad al conteo de los cruces de límites.
Hay una aceleración significativa (conocida desde 2001) del algoritmo del número de bobinado. Utiliza cruces señalizados, en función de si cada cruce es de izquierda a derecha o de derecha a izquierda. Los detalles y el código C ++ se proporcionan en el enlace de la siguiente anotación. [6] No se utilizan ángulos y no se involucra trigonometría. El código es tan rápido como el simple algoritmo de cruce de límites. Además, da la respuesta correcta para polígonos no simples, mientras que el algoritmo de cruce de límites falla en este caso.
Comparación
Ambos métodos se utilizan en SVG , donde el valor del atributo 'fill-rule' es " distinto de cero " o " evenodd ". Por ejemplo, en una superficie pentagonal regular no convexa , hay un agujero central con "evenodd" , ningún agujero con "distinto de cero" (dirección web: https://www.w3.org ).
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, 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 otros más simples que sean pares-impares-equivalentes antes de la verificación de intersección. [7] Sin embargo, esto es computacionalmente costoso. Es menos costoso utilizar el algoritmo de número de devanado rápido distinto de cero, que da el resultado correcto incluso cuando el polígono se superpone.
Point in polygon queries
El problema del punto en el polígono se puede considerar en la configuración de consulta geométrica repetida general : 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 ubicación de puntos planos . Existen soluciones más sencillas para algunos polígonos especiales.
Casos especiales
Los algoritmos más simples son posibles para los polígonos monótonas , en forma de estrella polígonos , 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 . [8] El método del producto escalar se extiende naturalmente a cualquier polígono convexo.
Referencias
- ^ Ivan Sutherland et al., "Una caracterización de diez algoritmos de superficie oculta" 1974, Encuestas de computación ACM vol. 6 no. 1.
- ^ "Point in Polygon, One More Time ..." Archivado el 24 de mayo de 2018 en Wayback Machine , Ray Tracing News , vol. 3 no. 4, 1 de octubre de 1990.
- ^ Shimrat, M., "Algoritmo 112: Posición del punto relativo al polígono" 1962, Comunicaciones del ACM Volumen 5 Número 8, agosto de 1962
- ^ Hormann, K .; Agathos, A. (2001). "El problema del punto en el polígono para polígonos arbitrarios". Geometría computacional . 20 (3): 131. doi : 10.1016 / S0925-7721 (01) 00012-8 .
- ^ Weiler, Kevin (1994), "An Incremental Angle Point in Polygon Test", en Heckbert, Paul S. (ed.), Graphics Gems IV , San Diego, CA, EE. UU .: Academic Press Professional, Inc., págs. 16– 23 , ISBN 0-12-336155-9.
- ^ Sunday, Dan (2001), Inclusión de un punto en un polígono.
- ^ Michael Galetzka, Patrick Glauner (2017). Un algoritmo par-impar simple y correcto para el problema de punto en polígono para polígonos complejos . Actas de la 12a Conferencia Internacional Conjunta sobre Teoría y Aplicaciones de Visión por Computadora, Imágenes y Gráficos por Computadora ( VISIGRAPP 2017), Volumen 1: GRAPP.
- ^ Prueba precisa del punto en el triángulo " ... los métodos más famosos para resolverlo "
Ver también
- Conjunto de topología de Java (JTS)
- Discusión: http://www.ics.uci.edu/~eppstein/161/960307.html
- Métodos de número de bobinado versus número de cruce: http://geomalgorithms.com/a03-_inclusion.html