Implementación del Algoritmo Ray Casting para la Detección de Puntos en Polígonos
Este documento presenta la implementación en código (similar a Java) del método de la Recta Paralela al Eje X, también conocido como Algoritmo Ray Casting, para determinar si un punto dado se encuentra dentro, fuera o en el límite de un polígono.
Función Principal: Verificación de Pertenencia
La función principal calcula el número de intersecciones entre un rayo horizontal que parte del punto P y los segmentos del polígono PL.
Documentación de la Función puntoEnPoligono
/**
* Verifica si un punto está en un polígono empleando la técnica de la recta paralela al eje X
* a partir del punto P.
*
* @param pl El polígono a evaluar.
* @param p El punto cuya pertenencia se desea verificar.
* @return 0, si el punto está en el límite (borde o vértice); 1, si está fuera; o -1, si el punto está dentro.
*/
Código de la Función puntoEnPoligono
public static int puntoEnPoligono(Poligono pl, Punto p) {
Punto p0, p1;
List<Punto> puntos;
int intersecciones = 0;
puntos = pl.getPuntos();
for (int i = 0; i < puntos.size() - 1; i++) {
p0 = puntos.get(i);
p1 = puntos.get(i + 1);
// 1. Punto en vértice o en segmento (límite)
if (puntoEnSegmento(p, p0, p1)) {
return 0;
}
// 2. P debe estar más a la derecha del segmento; de otra forma, se descarta.
if (p0.x <= p.x && p1.x <= p.x) {
continue;
}
// 3. El segmento es colineal con respecto a la recta R trazada desde P, se descarta.
if (p0.y == p.y && p1.y == p.y) {
continue;
}
// 4. Verifica si la recta R corta exactamente con un vértice del polígono.
if (p.y == p0.y || p.y == p1.y) {
// Los segmentos que estén abajo de R se descartan
if (p.y >= p0.y && p.y >= p1.y) {
continue;
}
}
// 5. Verifica si la recta R intersecta al segmento. Py debe estar entre las Ys de los puntos.
if ((p0.y <= p.y && p1.y > p.y) || (p1.y <= p.y && p0.y > p.y)) {
intersecciones++;
}
}
return cuentaIntersecciones(intersecciones);
}
Función Auxiliar: Conteo de Intersecciones
Esta función determina la posición final del punto basándose en la paridad del número de intersecciones encontradas.
private static int cuentaIntersecciones(int intersecciones) {
if (intersecciones % 2 == 0) {
return 1; // Par: Fuera del polígono
} else {
return -1; // Impar: Dentro del polígono
}
}
Función de Verificación de Segmento
La función puntoEnSegmento valida si el punto P se encuentra exactamente sobre el segmento definido por P0 y P1, incluyendo sus extremos.
/**
* Valida si el Punto intersecta con el segmento, incluyendo los extremos p0 y p1.
*/
private static boolean puntoEnSegmento(Punto p, Punto p0, Punto p1) {
// 1. El punto coincide con algún extremo
if ((p.x == p0.x && p.y == p0.y) || (p.x == p1.x && p.y == p1.y)) {
return true;
}
// 2. Recta con pendiente infinita (X = constante)
if (p0.x == p1.x) {
if (p.x == p0.x) {
return (p.y > p0.y && p.y < p1.y) || (p.y > p1.y && p.y < p0.y);
}
return false;
}
// 3. Recta con pendiente cero (Y = constante)
if (p0.y == p1.y && p0.y == p.y) {
return (p.x > p0.x && p.x < p1.x) || (p.x > p1.x && p.x < p0.x);
}
// 4. Recta con pendiente distinta de cero. La Y debe estar en el rango de las Y de p0 y p1.
if ((p.y > p0.y && p.y < p1.y) || (p.y > p1.y && p.y < p0.y)) {
// Checa si el punto P intersecta con el segmento evaluando la ecuación de la recta:
// y - y0 = (y1 - y0 / x1 - x0) * (x - x0)
return p.y - p0.y == (p1.y - p0.y) / (p1.x - p0.x) * (p.x - p0.x);
}
return false;
}