Hispanopedia Wiki
Articulo de referencia

Punto en un polígono

Un ejemplo de polígono simple En geometría computacional , el problema de punto en polígono ( PIP, por sus siglas en inglés) plantea si un punto dado en el plano se encuentra de...

Hispanopedia WikiContenido en espanolLectura gratuita
Un ejemplo de polígono simple

En geometría computacional , el problema de punto en polígono ( PIP, por sus siglas en inglés) plantea si un punto dado en el plano se encuentra dentro, fuera o sobre el límite de un polígono . Es un caso especial de problemas de localizació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 (SIG), 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 ( lanzamiento de rayos y suma de ángulos) en uso ya en 1974. [ 1 ]

Un intento de veteranos de los gráficos por computadora 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 ]

Algoritmo de trazado de rayos

El número de intersecciones de un rayo que pasa desde el exterior del polígono a cualquier punto: si es impar, indica que el punto está dentro del polígono; si es par, el punto está fuera del polígono. Esta prueba también funciona en tres dimensiones.

Una forma sencilla de determinar si un punto se encuentra dentro o fuera de un polígono simple consiste en comprobar cuántas veces un rayo , partiendo de dicho punto y dirigiéndose en cualquier dirección fija, interseca los bordes del polígono. Si el punto está fuera del polígono, el rayo lo intersecará un número par de veces. Si el punto está dentro del polígono, lo intersecará un número impar de veces. La condición de un punto dentro del borde del polígono depende de los detalles del algoritmo de intersección del rayo.

Este algoritmo también se conoce a veces como algoritmo del número de cruces o algoritmo de la regla par-impar , y se conocía ya en 1962. [ 3 ] El algoritmo se basa en una simple observación: si un punto se mueve a lo largo de un rayo desde el infinito hasta el punto de sondeo y cruza el límite de un polígono, posiblemente varias veces, entonces alternativamente va del exterior al interior, luego del interior al exterior, etc. Como resultado, después de cada dos "cruces de frontera", el punto en movimiento sale del polígono. Esta observación puede demostrarse matemáticamente utilizando el teorema de la curva de Jordan .

Precisión limitada

Si se implementa en un ordenador con aritmética de precisión finita , los resultados pueden ser incorrectos si el punto se encuentra muy cerca del límite, debido a errores de redondeo. Para algunas aplicaciones, como videojuegos u otros productos de entretenimiento, esto no supone un gran problema, ya que suelen priorizar la velocidad sobre la precisión. Sin embargo, para un programa informático formalmente correcto , habría que introducir una tolerancia numérica ε y comprobar 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 trazado de rayos comprueban consecutivamente las intersecciones de un rayo con todos los lados del polígono. En este caso, surge el siguiente problema: si el rayo pasa exactamente por un vértice del polígono, intersecará dos segmentos en sus extremos. Si bien esto no representa un problema para el vértice superior del ejemplo o el vértice entre los cruces 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 coinciden con el rayo. La solución es la siguiente: si el punto de intersección es un vértice de un lado del polígono analizado, la intersección solo se contabiliza si el otro vértice del lado se encuentra debajo del rayo. Esto equivale a considerar que los vértices que se encuentran sobre el rayo están ligeramente por encima de él.

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 como resultado el vértice en ambos casos. Si el polígono se especifica mediante sus vértices, este problema se elimina comprobando las coordenadas y del rayo y los extremos del lado del polígono analizado antes de calcular la intersección. En otros casos, cuando los lados del polígono se calculan a partir de otros tipos de datos, deben aplicarse otras técnicas para garantizar la robustez numérica del algoritmo.

Algoritmo de número de vueltas

Otra técnica para comprobar si un punto se encuentra dentro de un polígono consiste en calcular su número de vueltas con respecto al polígono. Si el número de vueltas es distinto de cero, el punto se encuentra dentro del polígono. Este algoritmo también se conoce como algoritmo de la regla de no cero .

Una forma de calcular el número de vueltas 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 ineficiente en términos de rendimiento (más lento) en comparación con el algoritmo de trazado de rayos. Por suerte, no es necesario calcular estas funciones trigonométricas inversas. Dado que el resultado, la suma de todos los ángulos, puede sumar 0 o2π{\displaystyle 2\pi }(o múltiplos de2π{\displaystyle 2\pi }) solamente, es suficiente rastrear por qué cuadrantes serpentea el polígono, [ 5 ] 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.

Visualización del algoritmo de número de vueltas de Dan Sunday . Un número de vueltas de 0 significa que el punto está fuera del polígono; otros valores indican que el punto está dentro del polígono.

En 2001, Dan Sunday desarrolló un algoritmo mejorado para calcular el número de vueltas. [ 6 ] Este algoritmo no utiliza ángulos ni trigonometría en sus cálculos, y funciona exactamente igual que los algoritmos de trazado de rayos descritos anteriormente. El algoritmo de Sunday considera un rayo horizontal infinito proyectado desde el punto que se está comprobando. Cada vez que ese rayo cruza una arista del polígono, se utiliza el algoritmo de cruce de aristas de Juan Pineda (1988) [ 7 ] para determinar cómo afectará el cruce al número de vueltas. Como lo describe Sunday, si la arista cruza el rayo en dirección ascendente, el número de vueltas se incrementa; si lo cruza en dirección descendente, se decrementa. El algoritmo de Sunday proporciona la respuesta correcta para polígonos no simples, mientras que el algoritmo de cruce de límites falla en este caso. [ 6 ]

Método de polígonos modificados

El método del polígono modificado, publicado en 2019, abarca tanto casos convexos como cóncavos, y se basa en la definición básica del tamaño del polígono (línea/área/volumen) en función de las dimensiones espaciales de la figura. El resultado es un método muy rápido y preciso en comparación con las técnicas existentes. [ 8 ]

Implementaciones

SVG

Métodos similares se utilizan en SVG para definir una forma de rellenar con color varias formas (como trazados, polilíneas, polígonos, texto, etc.). [ 9 ] El algoritmo de relleno está influenciado por el atributo 'fill-rule'. El valor puede ser o nonzero. evenoddPor 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 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 equivalentes par-impar antes de la verificación de intersección. [ 11 ] Sin embargo, esto es computacionalmente costoso. Es menos costoso usar el algoritmo rápido de número de vueltas distinto de cero, que da el resultado correcto incluso cuando el polígono se superpone a sí mismo.

Consultas de punto dentro de un polígono

El problema de un punto en un polígono puede considerarse dentro del contexto general de consultas geométricas repetidas : dado un polígono y una secuencia de puntos de consulta, se busca rápidamente la respuesta para cada punto. Es evidente que se puede utilizar cualquiera de los métodos generales para la localización de puntos en un plano . Existen soluciones más sencillas para algunos polígonos especiales.

Casos especiales

Es posible utilizar algoritmos más sencillos 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éntricas , una ecuación paramétrica o el producto escalar . [ 12 ] El método del producto escalar se extiende naturalmente a cualquier polígono convexo.

Referencias

  1. ↑ Ivan Sutherland et al.,"Una caracterización de diez algoritmos de superficie oculta" 1974, ACM Computing Surveys vol. 6 no. 1.
  2. ↑ Mark Vandewettering; Eric Haines; Edward John Kalenda; et  al. (1 de octubre de 1990), "Punto en polígono, una vez más..." , Ray Tracing News , 3 (4)
  3. ↑ Shimrat, M., "Algoritmo 112: Posición de un punto con respecto a un polígono", 1962, Communications of the ACM Volumen 5 Número 8, agosto de 1962. https://dl.acm.org/doi/10.1145/368637.368653
  4. ↑ 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 .
  5. ↑ 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
  6. 1 2 Sunday, Dan (2001). "Inclusión de un punto en un polígono" . Archivado del original el 26 de enero de 2013.
  7. ↑ Pineda, Juan (agosto de 1988). Un algoritmo paralelo para la rasterización de polígonos (PDF) . SIGGRAPH '88. Computer Graphics . Vol. 22, n.º 4. Atlanta . Consultado el 8 de agosto de 2021 .  
  8. ↑ El-Salamony, Mostafa (2019). "Método de polígono modificado para el problema de punto en polígono" (PDF) . VIII CONFERENCIA EUROPEA DE AERONÁUTICA Y CIENCIAS ESPACIALES (EUCASS) . 1 (1): 1– 9.
  9. ↑ "Pintura: relleno, trazo, colores y servidores de pintura – SVG Tiny 1.2" . www.w3.org . Consultado el 24 de julio de 2021 .
  10. ↑ "Pintura: relleno, trazo, colores y servidores de pintura – SVG Tiny 1.2" . www.w3.org . Consultado el 24 de julio de 2021 .
  11. ↑ 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 12.ª Conferencia Internacional Conjunta sobre Visión por Computadora, Imágenes y Teoría y Aplicaciones de Gráficos por Computadora ( VISIGRAPP 2017), Volumen 1: GRAPP.
  12. ↑ Punto preciso en la prueba del triángulo " ...los métodos más famosos para resolverlo "

Véase también

  • Suite de topología Java (JTS)
  • Debate: https://www.ics.uci.edu/~eppstein/161/960307.html
  • Métodos de número de vueltas frente a número de cruces: https://web.archive.org/web/20131210180851/http://geomalgorithms.com/a03-_inclusion.html , también disponible en Scribd https://www.scribd.com/document/735206906/Inclusion-of-a-Point-in-a-Polygon (se requiere suscripción)