Algoritmo Radial
El algoritmo radial [1] es un algoritmo utilizado principalmente en geometría computacional que evalúa la relación topológica de inclusión entre un punto y un polígono simple, lo que en matemáticas, y más concretamente, en topología, se denomina como el problema del Punto en polígono (Point in polygon, o PIP en sus siglas en inglés).
Aplicaciones
Su uso es particularmente relevante en los procesos que requieren gran precisión, especialmente en los Sistemas de Información Geográfica (SIG o GIS), CAD, o gráficos por computadora.
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.
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
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;
}
Referencias
- ↑ Error de Lua: Error interno: El intérprete ha finalizado con la señal "-129".
http://ojs.revistamapping.com/index.php?journal=MAPPING&page=issue&op=view&path%5B%5D=71
http://diccionario.raing.es/es/lema/algoritmo-radial