CODEWITHSUNDEEP
algorithmgeolocation
Paul Alexander
Paul Alexander

Reputation: 32367

latitude & longitude as coordinates adequate for point in polygon algorithm

Given a database of long/lat coordinates representing targets and a series of lat/long representing the bounding coordinates of polygons representing "zones". Using a simple ray casting algorithm is it safe to treat the lat/long as cartesian coordinates for determining if the target is within the zone?

Upvotes: 1

Views: 1633

Answers (3)

sandipshirsale
sandipshirsale

Reputation: 791

You can try this 

<html xmlns="http://www.w3.org/1999/xhtml">
<head id="Head1" runat="server">
    <title></title>
    <script type="text/javascript" src="https://maps.googleapis.com/maps/api/js?key=AIzaSyBfaExFhABnh7I3-vTHJjA4TWqtYnMccKE&sensor=false"></script>
    <script type="text/javascript" src="http://www.the-di-lab.com/polygon/jquery-1.4.2.min.js"></script>


<script type="text/javascript">
    var map;
    var boundaryPolygon;
    function initialize() {

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


        var mapProp = {
            center: new google.maps.LatLng(37.684, -122.591),
            zoom: 10,
            mapTypeId: google.maps.MapTypeId.ROADMAP
        };
        map = new google.maps.Map(document.getElementById("googleMap"), mapProp);



        google.maps.event.addListener(map, 'click', function (event) {
            if (boundaryPolygon!=null && boundaryPolygon.Contains(event.latLng)) {
                alert(event.latLng + " is inside the polygon");
            } else {
                alert(event.latLng + " is outside the polygon");
            }

        });
    }


    function btnCheckPointExistence_onclick() {
        var latitude = document.getElementById('txtLattitude').value;
        var longitude = document.getElementById('txtLongitude').value;
        //alert(latitude);     alert(longitude)
        var myPoint = new google.maps.LatLng(latitude, longitude);

        if (boundaryPolygon == null) {
            alert("No Polygon");
        }
        else {

            if (boundaryPolygon.Contains(myPoint)) {
                alert(myPoint + "is inside the polygon.");
            } else {
                alert(myPoint + "is 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) {

            if (boundaryPolygon.Contains(event.latLng)) {
                alert(event.latLng + "is inside the polygon.");
            } else {
                alert(event.latLng + "is outside the polygon.");
            }

        });

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

    }



  </script>
</head>
<body onload="initialize();drawPolygon();">
    <form id="form1" runat="server">

         <input type="text" value="28.982005022927137" name="txtLattitude" id="txtLattitude" placeholder="Enter Latitude">
        <input type="text" value="77.72157669067383" name="txtLongitude" id="txtLongitude" placeholder="Enter Langitude">
        <input type="button" value="Submit" name="submit" id="submit-text" value="submit" onclick="btnCheckPointExistence_onclick();">


        <h3>Check If Point Exist in a Polygon</h3>
        <span id="spnMsg" style="font-family: Arial; text-align: center; font-size: 14px; color: red;">this is message</span>
        <br />
        <br />

        <div id="googleMap" style="width: auto; height: 500px;">
        </div>

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

You can view Demo here

Upvotes: 1

Larry Watanabe
Larry Watanabe

Reputation: 10184

No, it's not safe to do that. You'll get anomalies around the poles and also at the 0 longitude areas.

Take a look at the NASA world wind code. they have representations for polygons on the surface of the globe although you have to be careful -- some of the representations will represent these anomalies, others will not.

http://worldwind.arc.nasa.gov/java/

Upvotes: 0

dave
dave

Reputation: 13280

Provided the edges are short, it should work well enough. It won't be "correct" though.

Imagine a triangle with two points a and b on the equator and one just short of the north pole. Evidently, (almost) all points with a longitude between a and b above the equator are in the triangle. But if we try treating the lats/longs as cartesian coordinates, we get something quite different...

Edit: You'll need to be careful with zones which cross longitude = max/min, and even more careful with the ones that also contain a pole

Upvotes: 3

Related Questions