Algoritmo radial

Un algoritmo radial es un algoritmo matemático que permite localizar si un punto en referencia a un polígono, situados ambos en el mismo plano, se encuentra dentro o fuera de este. Este problema para el cual otros algoritmos como el de Ray casting han intentado dar solución, se conoce como punto en polígono.

Aplicaciones

Se ha propuesto su uso en programas de geometría computacional que requieren mucha precisión, como los Sistemas de Información Geográfica SIG o GIS, diseño asistido por computadora CAD, y gráficos por computadora.[1]​

Descripción intuitiva

El procedimiento consiste en calcular la sumatoria de los ángulos de barrido formados por el conjunto de pares de vectores cuyos orígenes están en el punto y sus extremos en los vértices del polígono.

Sumatoria con signo.

Dichos pares de vectores se toman en el orden descrito por los vértices del polígono, y con el signo dependiente del sentido de crecimiento del ángulo. Habitualmente, se toma el sentido antihorario como positivo, y el sentido horario como negativo.

El algoritmo calcula un valor expresado en unidades angulares y, teóricamente, sólo son posibles dos resultados, aunque, debido a la limitada precisión de las computadoras, los valores obtenidos suelen no ser exactos. 

   0 rad (o un valor muy próximo)		Indica que el punto está fuera del polígono.
   2π rad (o un valor muy próximo)	        Indica que el punto está dentro del polígono.

No obstante, y en base a estos resultados, la implementación típica del algoritmo en un lenguaje de programación, se suele modificar para que devuelva uno de los siguientes tres valores discretos: 

   -1        Cuando el punto se encuentra fuera del polígono.
    0        Cuando el punto se encuentra exactamente sobre uno de los lados del polígono. Esta circunstancia se pone de manifiesto durante la
                 ejecución del algoritmo, cuando el valor absoluto del ángulo formado por uno de los pares de vectores resulta ser igual a π rad.
    1        Cuando el punto se encuentra dentro del polígono.

Pseudocódigo

Sentido positivo.
Sentido negativo.
 Función Punto_En_Polígono (Punto P, Vértice V[] )
 {
   suma = 0;
   // Bucle por todos los segmentos del polígono.
   Por (cada segmento S[i] formado por  V[i] y V[i+1] )
   {
       a = AnguloEntre(P, S[i]); // Ángulo con signo, desde V[i] hasta V[i+1]
       Si (|a| == π)
       {
	    Salir con Resultado = 0; // El punto está sobre el lado del polígono.
       }
       // Incrementar la suma de ángulos con signo.
       suma = suma + a;
   } Siguiente segmento.
   Si (suma == 0)  Salir con Resultado = -1;
   Si (suma == 2π) Salir con Resultado = 1;
 }

Véase también

Enlaces externos

Referencias

  1. ↑ Martín Arriarán, Miguel (Mayo de 2000). «El algoritmo Radial. Otra solución para el problema del Punto en Polígono.». Mapping, Revista Internacional de Geomática y Ciencias de la Tierra 9 (62): 20-22. Consultado el 23 de diciembre de 2019. 

Bibliografía