Solving the Point in Polygon Problem Using Google Maps and Fusion Tables

Question

The Point-In-Polygon problem is fairly well documented on this forum. My question is if there is a way to use Google's free tools, i.e. Google Maps, Fusion Tables, and possibly Google Refine, to solve this problem.

I am ultimately attempting to create a heat map of neighborhood boundaries. In basic language here are the steps that I wish to perform: 1. Geocode a list of home addresses using Fusion Table's built-in feature. This yields a set of lat/long coordinates for each address. 2. Import a Shapefile of polygons into Google Fusion to store the boundaries (polygon coordinates). *I am able to get this far.. The next steps are where I am looking for some guidance. 3. Apply a point-in-polygon algorithm to identify which addresses fall within each boundary. What is the simplest way to do this considering that I am ultimately attempting to color-code each polygon depending on the number of points that lie within its boundary lines.

Thanks,

Answer 1

Unfortunately none of the google api's support this query beyond simple rectangles or circles.

Your options are to pre-process using QGIS or the OGR API. Or you can implement the ray casting algorithm in JavaScript.

Also - check out the source of this example: http://www.geocodezip.com/v3_collection-map2e_FT.html

If you implement the algorithm yourself I'm not sure if you can use the loaded shapefile polygons as you would need access the coordinates but there are other ways around that issue.

Answer 2

As GeoSpatialpython.com mentioned, javascript based ray-casting is a good choice. Here is a script from tparkin : https://github.com/tparkin/Google-Maps-Point-in-Polygon/blob/master/maps.google.polygon.containsLatLng.js

It extends the google maps api v3 polygon class with a new method called containsLatLng which accepts a single LatLng object, which represents the point that you are actually checking against the polygon.

To import a shapefile into Fusion Tables, use http://www.shpescape.com/ which is really easy to use. After you are done importing, you can see that the polygons, stored in your shapefile are now in your Fusion Tables table in KML format.

Here comes the tricky part. Use Google Visualization query in Javascript, and with that query choose the polygons that you want to inspect. By this query, the KML formatted text will also be in the result set. Put that in a variable and put that variable between two string: <Placemark> </Placemark> (You can find some tutorials on the web about how to make google polygons from KML using Javascript) And finally, if you managed to transform that KML into a google maps api polygon object, you will be good to go with the ray casting algorithm.

If there is anything you don't understand or need help with, just shoot me a message here!

Answer 3

The Google maps API does not already provide a method for checking points in polygons. After researching a bit I stumbled across the Ray-casting algorithm which will determine if an X-Y coordinate is inside a plotted shape. This will translate to latitude and longitude. The following extends the google.maps.polygon.prototype to use this algorithm. Simply include this code at a point in the code after google.maps has loaded:

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

}

}; Here we have extended the functionality of google.maps.Polygon by defining a function with name ‘Contains’ which can be used to determine whether the latitude longitude provided in function parameter are within the polygon or not. Here we make use of Ray-casting algorithm and developed a function using the same. After doing this much of exercise now, we can check a point as follows:

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 }

For complete code and demo please go to: http://counsellingbyabhi.blogspot.in/2013/01/google-map-check-whether-point-latlong.html

Answer 4

This is a clean solution I implemented in Node.js based on the answer that @techabhi provided above.

/**
 * 
 * @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);
};