Problem
Description:
Discovering whether a point on a map is inside a polygon can be very useful, especially now that modern browsers and phones are location aware. If you can tell if your user is within a specific boundary then you can present them with immediately relevant information. There may be some another scenarios as well in which this requirement may be a need like for refining results within a particular area while getting results using Google Nearby Search API. So here we present a solution for the same.
Input:
We
have a Google map with a particular city drawn as a boundary polygon. We are
having the polygon geometry coordinates. Now we are to determine whether a
given latitude longitude exists within this polygon or not.
Solution:
The Google maps API does not already provide a method for checking points in
polygons.
After researching a bit I stumbled across the Ray-casting algorithm which will
determine if an X-Y coordinate is inside a plotted shape. This will translate
to latitude and longitude. The following extends the
google.maps.polygon.prototype to use this algorithm. Simply include this code
at a point in the code after google.maps has loaded:
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();
}
//
alter longitude to cater for 180 degree crossings
if (px < 0) { px += 360 };
if (ax < 0) { ax += 360 };
if (bx < 0) { bx += 360 };
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);
}
};
Here we have extended the functionality of google.maps.Polygon
by defining a function with name ‘Contains’ which can be used to determine
whether the latitude longitude provided in function parameter are within the
polygon or not.
Here we make use of Ray-casting algorithm and developed a function using the same.
After doing this much of exercise now,
we can check a point as follows:
var point = new google.maps.LatLng(52.05249047600099, -0.6097412109375);
var polygon = new google.maps.Polygon({path:[INSERT_PATH_ARRAY_HERE]});
if (polygon.Contains(point)) {
// point is inside polygon
}
The complete code is below the post. Copy and paste the code in notepad , save the file with html extension and then run the file with any browser.
I hope this post will be beneficial for the developers. Any feedback or comments are welcome.
I hope this post will be beneficial for the developers. Any feedback or comments are welcome.
Complete Code:
<!DOCTYPE html PUBLIC "-//W3C//DTD
XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<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">
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;
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 = '-97.370989999999992
46.992124, -97.370986 46.992287, -97.404366 46.992346, -97.40961 46.992432,
-97.409600000000012 46.993206, -97.409765 46.993213999999995, -97.410456
46.993027999999995, -97.410618 46.992433999999996, -97.41815 46.992459,
-97.396357 46.977869, -97.39667 46.977866999999996, -97.397527 46.978437,
-97.397883 46.978272, -97.397886 46.977869, -97.409083999999993 46.977903,
-97.408824 46.962755, -97.393744 46.962813, -97.393713999999989 46.962308,
-97.393385 46.96223, -97.393039 46.96236, -97.393025 46.962813999999995,
-97.387739 46.962816, -97.387783 46.972404999999995, -97.387827
46.972705999999995, -97.38839 46.97385, -97.38850699999999 46.974388,
-97.388545999999991 46.977838999999996, -97.357395 46.977753, -97.358465
46.978674, -97.358299 46.978932, -97.357631 46.979014, -97.357932999999989
46.979532, -97.357866 46.979744, -97.35763399999999 46.979887,
-97.356097999999989 46.980121999999994, -97.355798 46.980382999999996,
-97.35579899999999 46.980875999999995, -97.356401999999989 46.981840999999996,
-97.357171999999991 46.982386999999996, -97.35807299999999 46.982313,
-97.358240999999992 46.982431, -97.358108 46.982808, -97.358108 46.983089,
-97.35837699999999 46.983208999999995, -97.358944 46.983197, -97.359646
46.982938, -97.360737 46.983602999999995, -97.360731 46.984094999999996,
-97.360159 46.984359999999995, -97.360120999999992 46.984784999999995,
-97.360186 46.984942, -97.359913999999989 46.9853, -97.359338999999991
46.985768, -97.359367999999989 46.986126, -97.360064 46.986048, -97.360362
46.986134, -97.360756999999992 46.986557999999995, -97.360884 46.987162,
-97.360879 46.98761, -97.360575 46.987832999999995, -97.359294999999989
46.98793, -97.358824 46.988082999999996, -97.358820999999992 46.988329,
-97.359450999999993 46.988457, -97.359681999999992 46.988613, -97.35974
46.989374, -97.36 46.990001, -97.360295999999991 46.990379999999995, -97.360193
46.990671, -97.360188999999991 46.991006999999996, -97.360585 46.991273,
-97.361215 46.99131, -97.361444999999989 46.99151, -97.361351 46.992263,
-97.367206 46.992273, -97.367217 46.987584, -97.367831 46.988023,
-97.368158999999991 46.988174, -97.369042999999991 46.988375999999995,
-97.369925 46.988848999999995, -97.370021 46.989002, -97.369508 46.989149,
-97.36962 46.990027999999995, -97.369512 46.990314, -97.369994999999989
46.990925999999995, -97.369884 46.991344, -97.370989999999992 46.992124';
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.setCenter(boundarydata[0]);
boundaryPolygon.setMap(map);
}
Hello Abhishek,
ReplyDeleteThank you for such a wonderful post.
I have one question, how did you get the boundary data of a polygon?
kindly reply me on: mdrizwan_1@yahoo.co.in
Boundary data is nothing but the set of coordinates (latitude and longitude) on the map forming a cycle.
ReplyDeleteMeans the first coordinate and last coordinate should be the same. In the above post go through and analyze the variable 'var boundary' which contains the boundary data of a polygon.
You may get the boundary data for states , cities and other geographical location but mostly those are paid data.
Hello Abhishek,
DeleteThanks for your reply. I wanna now which method did you use to get the coordinates of a polygon. did you use path.getPath() or some another?. bcoz getPath returns only coordinates selected by user. i need all the coordinate in a polygon path (i.e., boundary). Any help appreciated?
Regards
kindly reply me on: mdrizwan_1@yahoo.co.in
Yaa...you can get the boundary coordinates by using getPath() method.
DeleteOk ok...First let me know how you are drawing the polygon on map, means by user intervention (by mouse) or by some other mechanism.?
using drawing library in google maps api
Deletethis is very much helpful...thanks bro...
ReplyDeleteAbhishek, This was really helpful. I want to exactly do the same on Android. Any help which libraries I need to use for Polygon mapping ?
ReplyDeleteGoogle has its own google maps api for android as well. So use them. :)
DeleteIs this possible to search for points inside a polygon on the fly?
ReplyDeleteI.e. a user fills an area in the search box,e.g. "London" and it returns all points inside that area.
Is this possible,if so how?
thanks!
Abhishek, thanks for your post.
ReplyDeleteYour implementation was very helpful for my testing purposes.
Actually, i tweak it a little, to make it work with an array of arrays like this one: [[lat,long],[lat,long],...]
Thanks a lot !! Really works for me ! :)
ReplyDeleteJust amazing! Thanks a lot
ReplyDeleteWhy is the order of latlong the other way on:-
ReplyDeleteboundarydata[i] = new google.maps.LatLng(latlong[1], latlong[0]);
Isn't it suppose to be:-
boundarydata[i] = new google.maps.LatLng(latlong[0], latlong[1]);
Actually in the example , the boundary data is in order of(long,lat). Thats why.
DeleteHi, I have a KML File with set of polygon data. Now i need to found, given long and lat values within that polygon or not?
Delete@seetaram did you find any solution for your query??
Deletehi tried to use this code but its not working for me, can you give working code
ReplyDeleteHi, I posted a question on StackOverflow http://stackoverflow.com/questions/27930459/add-multiple-values-from-markers-inside-polygon-google-map-v3-tooltip-display asking how to go about adding up values from multiple markers within a circle or polygon. Could you give me some guidance on how to go about this? Thanks in Advance for any help...
ReplyDeleteHi, I posted a question on StackOverflow http://stackoverflow.com/questions/27930459/add-multiple-values-from-markers-inside-polygon-google-map-v3-tooltip-display asking how to go about adding up values from multiple markers within a circle or polygon. Could you give me some guidance on how to go about this? Thanks in Advance for any help... (Posted again because my question disappeared!)
ReplyDeletewhat is the possible couse for TypeError: a is null while running the page and inspecting the error
ReplyDeletewhat is the possible couse for the following error while i get when i run the page on firefox and inspecting the error TypeError: a is null
ReplyDeletethis example is not working , can you please help me
ReplyDelete