Resolución del problema del punto en el polígono mediante Google Maps y Fusion Tables

Question

El problema del punto en el polígono está bastante bien documentado en este foro. Mi pregunta es si hay una manera de utilizar las herramientas gratuitas de Google, es decir, Google Maps, Fusion Tables, y posiblemente Google Refine, para resolver este problema.

En definitiva, estoy intentando crear un mapa de calor de los límites del barrio. En lenguaje básico estos son los pasos que deseo realizar: 1. 1. Geocodificar una lista de direcciones de casas utilizando la función incorporada de Fusion Table. Esto produce un conjunto de coordenadas lat/long para cada dirección. 2. 2. Importar un Shapefile de polígonos a Google Fusion para almacenar los límites (coordenadas de los polígonos). *Puedo llegar hasta aquí.. Los siguientes pasos son donde estoy buscando un poco de orientación. 3. Aplicar un algoritmo de punto en polígono para identificar qué direcciones caen dentro de cada límite. ¿Cuál es la forma más sencilla de hacerlo, teniendo en cuenta que, en última instancia, estoy tratando de codificar por colores cada polígono en función del número de puntos que se encuentran dentro de sus líneas limítrofes?

Gracias,

Answer 1

Lamentablemente ninguna de las api's de google soporta esta consulta más allá de simples rectángulos o círculos.

Tus opciones son preprocesar usando QGIS o la API OGR. O puedes implementar el algoritmo de fundición de rayos en JavaScript.

Además, consulte la fuente de este ejemplo: http://www.geocodezip.com/v3_collection-map2e_FT.html

Si implementas el algoritmo tú mismo, no estoy seguro de que puedas utilizar los polígonos del shapefile cargado, ya que necesitarías acceder a las coordenadas, pero hay otras formas de evitar ese problema.

Answer 2

Como mencionó GeoSpatialpython.com, el ray-casting basado en javascript es una buena opción. Aquí hay un script de tparkin : https://github.com/tparkin/Google-Maps-Point-in-Polygon/blob/master/maps.google.polygon.containsLatLng.js

Extiende la clase google maps api v3 polygon con un nuevo método llamado containsLatLng que acepta un único objeto LatLng, que representa el punto que realmente se está comprobando con el polígono.

Para importar un shapefile a Fusion Tables, utilice http://www.shpescape.com/ que es realmente fácil de usar. Una vez que haya terminado de importar, podrá ver que los polígonos, almacenados en su archivo shape, están ahora en su tabla de Fusion Tables en formato KML.

Aquí viene la parte complicada. Utiliza la consulta de Google Visualization en Javascript, y con esa consulta elige los polígonos que quieres inspeccionar. Con esta consulta, el texto con formato KML también estará en el conjunto de resultados. Ponga eso en una variable y ponga esa variable entre dos cadenas: <Placemark> </Placemark> (Puedes encontrar algunos tutoriales en la web sobre cómo hacer polígonos de google a partir de KML usando Javascript) Y por último, si has conseguido transformar ese KML en un objeto poligonal de la api de google maps, estarás bien con el algoritmo de ray casting.

Si hay algo que no entiendas o con lo que necesites ayuda, envíame un mensaje aquí.

Answer 3

La API de Google Maps no proporciona aún un método para comprobar los puntos en los polígonos. Después de investigar un poco me topé con el algoritmo Ray-casting que determinará si una coordenada X-Y está dentro de una forma trazada. Esto se traducirá en latitud y longitud. Lo siguiente extiende el google.maps.polygon.prototype para utilizar este algoritmo. Simplemente incluya este código en un punto del código después de que google.maps haya cargado:

google.maps.Polygon.prototype.Contains = function(point) { var crossings = 0, path = this.getPath();

// for each edge
for (var i=0; i < path.getLength(); i++) {
    var a = path.getAt(i),
        j = i + 1;
    if (j >= path.getLength()) {
        j = 0;
    }
    var b = path.getAt(j);
    if (rayCrossesSegment(point, a, b)) {
        crossings++;
    }
}

// odd number of crossings?
return (crossings % 2 == 1);

function rayCrossesSegment(point, a, b) {
    var px = point.lng(),
        py = point.lat(),
        ax = a.lng(),
        ay = a.lat(),
        bx = b.lng(),
        by = b.lat();
    if (ay > by) {
        ax = b.lng();
        ay = b.lat();
        bx = a.lng();
        by = a.lat();
    }
    // alter longitude to cater for 180 degree crossings
    if (px < 0) { px += 360 };
    if (ax < 0) { ax += 360 };
    if (bx < 0) { bx += 360 };

    if (py == ay || py == by) py += 0.00000001;
    if ((py > by || py < ay) || (px > Math.max(ax, bx))) return false;
    if (px < Math.min(ax, bx)) return true;

    var red = (ax != bx) ? ((by - ay) / (bx - ax)) : Infinity;
    var blue = (ax != px) ? ((py - ay) / (px - ax)) : Infinity;
    return (blue >= red);

}

}; Aquí hemos extendido la funcionalidad de google.maps.Polygon definiendo una función con nombre 'Contains' que puede ser usada para determinar si la latitud y longitud proporcionadas en el parámetro de la función están dentro del polígono o no. Aquí hacemos uso del algoritmo Ray-casting y desarrollamos una función utilizando el mismo. Después de hacer este ejercicio ahora, podemos comprobar un punto de la siguiente manera:

var point = new google.maps.LatLng(52.05249047600099, -0.6097412109375); var polygon = new google.maps.Polygon({path:[INSERT_PATH_ARRAY_HERE]}); if (polygon.Contains(point)) { // point is inside polygon }

Para ver el código completo y la demostración, diríjase a http://counsellingbyabhi.blogspot.in/2013/01/google-map-check-whether-point-latlong.html

Answer 4

Esta es una solución limpia que implementé en Node.js basada en la respuesta que @techabhi proporcionó arriba.

/**
 * 
 * @param {array} point 
 * @param {Array} vs 
 */
function isInsidePolygon(point, geoFencePoints) {
    let crossings = 0;

    for (let index = 0; index < geoFencePoints.length; index++) {
        const a = geoFencePoints[index];

        let j = index + 1;

        if (j >= geoFencePoints.length) {
            j = 0;
        }

        const b = geoFencePoints[j];

        if (_rayCrossesSegment(point, a, b)) {
            crossings++;
        }
    }

    return (crossings % 2 == 1);
};

/**
 * Ray Crosses segment
 * @param {Array} point
 * @param {Object} a
 * @param {Object} b
 */
const _rayCrossesSegment = (point, a, b) => {
    let currentPointLongitude = point[1],
        currentPointLatitude = point[0],
        longitudeA = a.lng,
        latitudeA = a.lat,
        longitudeB = b.lng,
        latitudeB = b.lat;

    if (latitudeA > latitudeB) {
        longitudeA = b.lng;
        latitudeA = b.lat;
        longitudeB = a.lng;
        latitudeB = a.lat;
    }
    // alter longitude to cater for 180 degree crossings
    if (currentPointLongitude < 0) {
        currentPointLongitude += 360
    };

    if (longitudeA < 0) {
        longitudeA += 360
    };

    if (longitudeB < 0) {
        longitudeB += 360
    };

    if (currentPointLatitude == latitudeA || currentPointLatitude == latitudeB) {
        currentPointLatitude += 0.00000001;
    }

    if ((currentPointLatitude > latitudeB || currentPointLatitude < latitudeA) || (currentPointLongitude > Math.max(longitudeA, longitudeB))) {
        return false;
    }

    if (currentPointLongitude < Math.min(longitudeA, longitudeB)) {
        return true;
    }

    const intersectionA = (longitudeA != longitudeB) ? ((latitudeB - latitudeA) / (longitudeB - longitudeA)) : -1;

    const intersectionB = (longitudeA != currentPointLongitude) ? ((currentPointLatitude - latitudeA) / (currentPointLongitude - longitudeA)) : -1;

    return (intersectionB >= intersectionA);
};