CODEWITHSUNDEEP
geometrygeospatial
ahwulf
ahwulf

Reputation: 2584

Given a polygon in latitude and longitude and a set of points, determine which points lie inside

Given a set of latlon points that make up a polygon, and a set of latlon points, how can I determine which points lie inside. The polygon may be up to 100km across and the error could be a few hundred meters (i.e. points inside or outside can fail or be included incorrectly at the edges). The polygons and points won't be near the poles. Can I treat the latlon points as 2d, or do I need to convert them to a projection of some kind? Circles are easy but I wonder if the error will be too great for a 100km wide polygon?

I plan to do this in C++ but the language doesn't matter.

Upvotes: 1

Views: 1783

Answers (2)

sandipshirsale
sandipshirsale

Reputation: 791

You can view actual demo here

<html xmlns="http://www.w3.org/1999/xhtml">
<head runat="server">
    <title>How to Check If Point Exist in a Polygon - Google Maps API v3</title>
    <script type="text/javascript" src="http://www.the-di-lab.com/polygon/jquery-1.4.2.min.js"></script>
    <script type="text/javascript" src="https://maps.googleapis.com/maps/api/js?v=3.exp&sensor=false"></script>
    <script type="text/javascript">
        var map;
        var boundaryPolygon;
        function initialize() {

            var mapProp = {
                center: new google.maps.LatLng(26.038586842564317, 75.06787185438634),
                zoom: 6,
                mapTypeId: google.maps.MapTypeId.ROADMAP
            };

            map = new google.maps.Map(document.getElementById("map-canvas"), mapProp);

            google.maps.Polygon.prototype.Contains = function (point) {
                // ray casting alogrithm http://rosettacode.org/wiki/Ray-casting_algorithm
                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();
                    }
                    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);
                }
            };


            google.maps.event.addListener(map, 'click', function (event) {

                if (boundaryPolygon != null && boundaryPolygon.Contains(event.latLng)) {
                    alert("in")
                    document.getElementById("spnMsg").innerText = "This location is " + event.latLng + " inside the polygon.";
                } else {
                    alert("out")
                    document.getElementById("spnMsg").innerText = "This location is " + event.latLng + " outside the polygon.";
                }

            });
        }


        function drawPolygon() {

            initialize();
            var boundary = '77.702866 28.987153, 77.699776 28.978594 ,77.735996 28.974164 ,77.719946 28.99346 ,77.713423 28.994361 ,77.711706 28.990382 ';
            var boundarydata = new Array();

            var latlongs = boundary.split(",");

            for (var i = 0; i < latlongs.length; i++) {
                latlong = latlongs[i].trim().split(" ");
                boundarydata[i] = new google.maps.LatLng(latlong[1], latlong[0]);
            }

            boundaryPolygon = new google.maps.Polygon({
                path: boundarydata,
                strokeColor: "#0000FF",
                strokeOpacity: 0.8,
                strokeWeight: 2,
                fillColor: 'Red',
                fillOpacity: 0.4

            });

            google.maps.event.addListener(boundaryPolygon, 'click', function (event) {
                document.getElementById("spnMsg").innerText = '';
                if (boundaryPolygon.Contains(event.latLng)) {
                    document.getElementById("spnMsg").innerText = "This location is " + event.latLng + " inside the polygon.";
                } else {
                    document.getElementById("spnMsg").innerText = "This location is " + event.latLng + " outside the polygon.";
                }

            });
            map.setZoom(14);
            map.setCenter(boundarydata[0]);
            boundaryPolygon.setMap(map);

        }

    </script>
</head>
<body onload="initialize();drawPolygon();">
    <form id="form1" runat="server">
        <h3>Check If Point Exist in a Polygon</h3>
        <h3>click on the polygon and out side the polygon for testing</h3>
        <span id="spnMsg" style="font-family: Arial; text-align: center; font-size: 14px; color: red;">this is message</span>
        <br />
        <br />
        <div id="map-canvas" style="width: auto; height: 500px;">
        </div>

    </form>
</body>
</html>

you can view more demos may be use full to you here http://codeace.in/download/gmap/

you can download all the demo by click on the file

"googlemap.zip" given in the index

Upvotes: 1

fastr.de
fastr.de

Reputation: 1523

Here is the (javascript) code from Openlayers to do it

/**
 * Method: containsPoint
 * Test if a point is inside a polygon.  Points on a polygon edge are
 *     considered inside.
 *
 * Parameters:
 * point - {<OpenLayers.Geometry.Point>}
 *
 * Returns:
 * {Boolean | Number} The point is inside the polygon.  Returns 1 if the
 *     point is on an edge.  Returns boolean otherwise.
 */
containsPoint: function(point) {
    var numRings = this.components.length;
    var contained = false;
    if(numRings > 0) {
        // check exterior ring - 1 means on edge, boolean otherwise
        contained = this.components[0].containsPoint(point);
        if(contained !== 1) {
            if(contained && numRings > 1) {
                // check interior rings
                var hole;
                for(var i=1; i<numRings; ++i) {
                    hole = this.components[i].containsPoint(point);
                    if(hole) {
                        if(hole === 1) {
                            // on edge
                            contained = 1;
                        } else {
                            // in hole
                            contained = false;
                        }                            
                        break;
                    }
                }
            }
        }
    }
    return contained;
}

Complete file can be found at Openlayers at Github To get the idea behind this.components have a look at Collection.js

update:

In OpenLayers a polygon is a collection of linear rings. the containsPoint functon of this can be found at LinearRing.js

Upvotes: 1

Related Questions