Punto en polígono
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]
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 de fronteras", 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".
