CODEWITHSUNDEEP
javascriptmathgoogle-maps-api-3coordinates
FabianCook
FabianCook

Reputation: 20557

Finding if a point is in a polygon

I have this code here that is attempting to work out if a point latLng passes through a polygon Maps.area.

Maps.ui.contains = function(latLng){
    //poly.getBounds gets the 'box' around the polygon
    if(!Maps.ui.getBounds().contains(latLng))
        return false;
    //So we dont need to check t/f, we either set it or we dont
    var inPolygon = false;
    var count = 0;

    Maps.area.getPaths().forEach(function(el0, index0){
        var last = el0.getLength() - 1;
        el0.forEach(function(el1, index1){
            count += Maps.ui.ray_intersect_segment(latLng, el1, el0.getAt(last));
            last = index1; 
        });
    });

    if(Maps.area.getPaths().getLength()%2 == 0)
        return count%2==0;
    else
        return count%2!=0;


}

var eps = 0.0001;
var inf = 1e600;
Maps.ui.ray_intersect_segment = function(point, i1, i2){
    var p = point;
    var segment = (i1.lng() > i2.lng())?[i2, i1]:[i1, i2];

    p = (p.lng() == segment[0].lng() || p.lng() == segment[1].lng())?new google.maps.LatLng(p.lng() + eps):p;

    if(p.lng() < segment[0].lng() || p.lng() > segment[1].lng() || p.lat() > [segment[0].lat(), segment[1].lng()].max())
        return 0;
    if(p.lat() < [segment[0].lat(), segment[1].lat()].min())
        return 1;

    var a = (segment[0].lat() != segment[1].lat())?(segment[1].lng() - segment[0].lng())/(segment[1].lat() - segment[0].lat()):inf;
    var b = (segment[0].lat() != p.lat()) ? (p.lng() - segment[0].lng())/(p.lat() - segment[0].lat()):inf;

    return (b > a)?1:0;
}

Maps.ui.getBounds = function() {
    //Lets make a box
    var bounds = new google.maps.LatLngBounds();
    //Get all the points lines of the polly
    var paths = Maps.area.getPaths();
    for (var p = 0; p < paths.getLength(); p++)
        //To store each path
        var path = paths.getAt(p);
        //Now lets expand the box
        for (var i = 0; i < path.getLength(); i++)
            //Add each point of the line to the 'box' making it bigger each time
            bounds.extend(path.getAt(i));
    //Reaturn the bounds, this has a contains method so we can check if the latLng is in it. 
    return bounds;
}

Array.prototype.max = function() {
  return Math.max.apply(null, this)
}

Array.prototype.min = function() {
  return Math.min.apply(null, this)
}

But I can't seem to work it out. For a simple triangle or square it works perfectly, but when we get to something like this it doesn't work because we can't figure out whether count should be even or odd

enter image description here

Upvotes: 3

Views: 378

Answers (2)

archsynthe
archsynthe

Reputation: 1

This is a pretty standard problem for geographical information systems. There are several "standard" algorithms for solving the problem. The link below notes a few of them and provides an example. Note that the algorithms tend to break down in edge cases, such as when the polygon spans the extreme lat/lon boundaries such as the poles and meridian.

Polygon Algorithms

Upvotes: 0

geocodezip
geocodezip

Reputation: 161334

The Google Maps API v3 spherical geometry library has the poly.contains. Takes a LatLng and a Polygon and tells you if the point is in the polygon.

containsLocation(point:LatLng, polygon:Polygon)

Upvotes: 2

Related Questions