Reputation: 2584
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
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
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