gpolygon

Check if a polygon contains a coordinate in Google Maps

At work, I've been tasked with a neat little project where a user can select a list of users represented by markers on a Google map by editing a polygon to surround the markers with. However, to my dismay, I could not find any methods in the API to see if a polygon contains a coordinate. I also had a hard time finding an algorithm so that I could implement it. I later learned this type of algorithm is called Point in Polygon (PiP).

First I tried the winding number algorithm (http://en.wikipedia.org/wiki/Point_in_polygon) but failed. I didn't put too much time into it since it is so CPU-intesive anyway. Then I came across an article on MSDN (http://msdn.microsoft.com/en-us/library/cc451895.aspx) which I adopted into Javascript. I extended the GPolygon class with a new method called containsLatLng, just like the GLatLngBounds class. The difference is that the method in the GLatLngBounds class will only get the 4 coordinates of the bounding box, which are the farthest points in the polygon, and see if the coordinate lies within that box. My method, however, does true collision detection to see if the point lies within any shape polygon with as many sides as you want. It worked out perfectly.

Without any further ado, here is the code [js/gmaps.polygon.containsLatLng.js]:

// Create polygon method for collision detection
GPolygon.prototype.containsLatLng = function(latLng) {
    // Do simple calculation so we don't do more CPU-intensive calcs for obvious misses
    var bounds = this.getBounds();
   
    if(!bounds.containsLatLng(latLng)) {
        return false;
    }
   
    var numPoints = this.getVertexCount();
    var inPoly = false;
    var i;
    var j = numPoints-1;
   
    for(var i=0; i < numPoints; i++) {
        var vertex1 = this.getVertex(i);
        var vertex2 = this.getVertex(j);
       
        if (vertex1.lng() < latLng.lng() && vertex2.lng() >= latLng.lng() || vertex2.lng() < latLng.lng() && vertex1.lng() >= latLng.lng())  {
            if (vertex1.lat() + (latLng.lng() - vertex1.lng()) / (vertex2.lng() - vertex1.lng()) * (vertex2.lat() - vertex1.lat()) < latLng.lat()) {
                inPoly = !inPoly;
            }
        }
       
        j = i;
    }
   
    return inPoly;
};

And here is the sample usage [index.htm]:

<html>
<head>
    <title>GIS Test</title>
    <script src="http://maps.google.com/maps?file=api&amp;v=2&amp;key=ABQIAAAAOzwQ7Lh4CqiMto5Mx5BruhRP7uQ16ovEZegyAfeetOdXUUHv1xQhaNqllcioqRUJo6b7JhhTgJZNyw" type="text/javascript"></script>
    <script src="js/gmaps.polygon.containsLatLng.js" type="text/javascript"></script>
    <script type="text/javascript">
    var isEditing = false;
    var polygon = null;
    var map = null;
    var isCompatible = GBrowserIsCompatible();
    var markers = [];
    var iconIncluded = 'http://maps.google.com/mapfiles/dd-start.png';
    var iconExcluded = 'http://maps.google.com/mapfiles/dd-end.png';
       
        function editClick() {
                isEditing = !isEditing;
                       
                if(isEditing && polygon != null) {
                        document.getElementById('edit_button').innerHTML = 'Stop Editing';
                        document.getElementById('help').innerHTML = 'Click to add points to your selection.';
                        document.getElementById('reset_button').disabled = 'disabled';
                        polygon.enableDrawing();
                } else {
                        document.getElementById('edit_button').innerHTML = 'Edit Selection';
                        document.getElementById('reset_button').disabled = '';
                        document.getElementById('help').innerHTML = 'Click "Edit Selection" to select users.';
                        polygon.disableEditing();
                }
        }
       
        // Update all markers with in poly status
        function updatePoints() {
                for(var i in markers) {
                        var marker = markers[i];
                        var point = marker.getLatLng();
                        var inPoly = polygon.containsLatLng(point);
                       
                        if(inPoly) {
                                marker.setImage(iconIncluded);
                        } else {
                                marker.setImage(iconExcluded);
                        }
                }
        }
       
        function resetPolygon() {
                if(polygon != null) {
                        map.removeOverlay(polygon);
                }
               
                polygon = new GPolygon([], "#000000", 1, 1, "#336699", 0.3);
                map.addOverlay(polygon);
               
                GEvent.addListener(polygon, "lineupdated", function() {
                        setTimeout(updatePoints, 50);
                });
               
                GEvent.addListener(polygon, "endline", function() {
                        setTimeout(editClick, 50);
                });
               
                updatePoints();
        }

    //<![CDATA[
    function load() {
        if (isCompatible) {
            // Create Map
            map = new GMap2(document.getElementById("map"));
            map.setCenter(new GLatLng(40, -90), 3);

            // Add controls
            map.addControl(new GLargeMapControl());
            map.addControl(new GMapTypeControl());

            // Create Selection Polygon
            var latlng = map.getCenter();
            var width = 20;
            var height = 12;
            var lat = latlng.lat();
            var lng = latlng.lng();
            var x1 = lng - width / 2;
            var y1 = lat - height / 2;
            var x2 = lng + width / 2;
            var y2 = lat + height / 2;
                       
                        resetPolygon();

            // Add 10 markers to the map at random locations
            var bounds = map.getBounds();
            var southWest = bounds.getSouthWest();
            var northEast = bounds.getNorthEast();
            var lngSpan = northEast.lng() - southWest.lng();
            var latSpan = northEast.lat() - southWest.lat();

            for (var i = 0; i < 100; i++) {
                var point = new GLatLng(southWest.lat() + latSpan * Math.random(), southWest.lng() + lngSpan * Math.random());
                var marker = new GMarker(point, {bouncy: true, title: "Customer " + i, autoPan: false});
                map.addOverlay(marker);
                marker.bindInfoWindowHtml("This is customer info " + i);
                markers.push(marker);
            }
           
            updatePoints();
        }
    }
    //]]>
    </script>
</head>
<body onload="load()" onunload="GUnload()">
    <div>
        <span><button id="edit_button" onclick="editClick()" type="button">Edit Selection</button></span>
        <span><button id="reset_button" onclick="resetPolygon()" type="button">Reset Selection</button></span>
        <span id="help" style="color: #666;">Click "Begin Editing" to select users.</span>
    </div>
    <hr />
    <div id="map" style="width: 640; height: 480; border:1px solid #333;"></div>
</body>
</html>

Sample: http://dawsdesign.com/Samples/GIS/
Download: http://dawsdesign.com/Samples/GIS/GIS.zip

Syndicate content