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;
}