Algoritmo del punto en un polígono en PHP

El algoritmo del punto en un polígono permite comprobar mediante programación si un punto está dentro de un polígono o fuera de ello. Una forma común de abordar el problema es contar cuántas veces una línea trazada desde el punto (en cualquier dirección) se cruza con el borde del polígono. Si lo cruza un número par de veces (o ninguna), entonces el punto está fuera. Si lo cruza un número impar de veces, el punto está dentro. Funciona incluso para formas complejas que tienen muchas coordenadas y por lo tanto crean borde muy detallado.

class pointLocation {

    var $pointOnVertex = true; // Checar si el punto se encuentra exactamente en uno de los vértices?

    function pointLocation() {

    }

        function pointInPolygon($point, $polygon, $pointOnVertex = true) {

        $this->pointOnVertex = $pointOnVertex;

        // Transformar la cadena de coordenadas en matrices con valores «x» e «y»

        $point = $this->pointStringToCoordinates($point);

        $vertices = array();

        foreach ($polygon as $vertex) {

            $vertices[] = $this->pointStringToCoordinates($vertex);

        }

        // Checar si el punto se encuentra exactamente en un vértice

        if ($this->pointOnVertex == true and $this->pointOnVertex($point, $vertices) == true) {

            return «vertex»;

        }

        // Checar si el punto está adentro del poligono o en el borde

        $intersections = 0;

        $vertices_count = count($vertices);

        for ($i=1; $i < $vertices_count; $i++) {

            $vertex1 = $vertices[$i-1];

            $vertex2 = $vertices[$i];

            if ($vertex1[‘y’] == $vertex2[‘y’] and $vertex1[‘y’] == $point[‘y’] and $point[‘x’] > min($vertex1[‘x’], $vertex2[‘x’]) and $point[‘x’] < max($vertex1[‘x’], $vertex2[‘x’])) { // Checar si el punto está en un segmento horizontal

                return «boundary»;

            }

            if ($point[‘y’] > min($vertex1[‘y’], $vertex2[‘y’]) and $point[‘y’] <= max($vertex1[‘y’], $vertex2[‘y’]) and $point[‘x’] <= max($vertex1[‘x’], $vertex2[‘x’]) and $vertex1[‘y’] != $vertex2[‘y’]) {

                $xinters = ($point[‘y’] – $vertex1[‘y’]) * ($vertex2[‘x’] – $vertex1[‘x’]) / ($vertex2[‘y’] – $vertex1[‘y’]) + $vertex1[‘x’];

                if ($xinters == $point[‘x’]) { // Checar si el punto está en un segmento (otro que horizontal)

                    return «boundary»;

                }

                if ($vertex1[‘x’] == $vertex2[‘x’] || $point[‘x’] <= $xinters) {

                    $intersections++;

                }

            }

        }

        // Si el número de intersecciones es impar, el punto está dentro del poligono.

        if ($intersections % 2 != 0) {

            return «inside»;

        } else {

            return «outside»;

        }

    }

    function pointOnVertex($point, $vertices) {

        foreach($vertices as $vertex) {

            if ($point == $vertex) {

                return true;

            }

        }

    }

    function pointStringToCoordinates($pointString) {

        $coordinates = explode(» «, $pointString);

        return array(«x» => $coordinates[0], «y» => $coordinates[1]);

    }

}

Una función que parece sencilla y de poca utilidad pero que en verdad es bastante interesante , hasta se puede usar con coordenadas de googlemaps.. La misma devuelve uno de estos 4 posibles valores:

inside (= adentro) si el punto está dentro del polígono.
outside (= afuera) si el punto está fuera del polígono.
vertex (= vértice) si el punto se encuentra exactamente en un vértice Y $pointOnVertex = true (line 2)
boundary (= borde) si el punto está en un segmento. Si $pointOnVertex = false, entonces también se devolverá boundary si el punto se encuentra en un vértice.

Lo vi en http://assemblysys.com/