In today’s world, Pioneering GIS is an another way of empowering the businesses and gaining a competitive advantage with location intelligence.
In this blog, we will learn how to find out whether given points(coordinates) are inside or outside the polygon. In my GIS project, I have used leaflet open source JavaScript library which has PointInPolygon() plugin for finding the position of the coordinates. Another Javascript function used to find the position of the coordinates/points is based on Ray Casting algorithm. We will see both the solutions one by one.
In above image, Point ‘A’ is outside the Polygon, Point ‘B’ is on the polygon boundary while Point ‘C’ is inside the Polygon. Let’s understand.
Leaflet.PointInPolygon() : This Leaflet plugin provides point-in-polygon function. This function is based on Dan Sunday’s C++ winding number implementation. The winding number accurately determines whether a point is inside a non-simple closed polygon. The points on the boundary and vertices are considered to be included in the polygon.
Code:
// Create Polygon
var mypolygon = L.polygon([
[51.51, -0.08],
[51.503, -0.06],
[51.51, -0.047]
]).addTo(mymap);
// Create Polygon
var mypolygon = L.polygon([
[51.51, -0.08],
[51.503, -0.06],
[51.51, -0.047]
]).addTo(mymap);
var result = mypolygon.getBounds().contains(p1.getLatLng());
If point is within polygon then it returns true. This function will only return true, if the point is within the bounding rectangle of the polygon.
Ray Casting algorithm: Ray casting algorithm can be used for checking whether a point is inside or outside the polygon.
Algorithm:
“When a point is given, then we virtually draw a line from a point far away outside from the polygon to the given point. Then, we calculate the number of intersections of the virtual line with the edges of the polygon. If the number of intersections is odd, then according to the Ray Casting theory we can conclude that the point is inside the polygon. Otherwise, the point is outside the polygon.”
Code :
var x = L.lat, y = L.lng;
var inside = false;
var intersections = 0;
var ss = ”;
for (var i = 0, j = polyPoints.length – 1; i < polyPoints.length; j = i++) {
var xi = polyPoints[i].lat, yi = polyPoints[i].lng; var xj = polyPoints[j].lat, yj = polyPoints[j].lng;
if (yj == yi && yj == y && x > Math.min(xj, xi) && x < Math.max(xj, xi)) { // Check if point is on an horizontal polygon boundary
return true;
}
if (y > Math.min(yj, yi) && y <= Math.max(yj, yi) && x <= Math.max(xj, xi) && yj != yi) {
ss = (y – yj) * (xi – xj) / (yi – yj) + xj;
if (ss == x) { // Check if point is on the polygon boundary (other than horizontal)
return true;
}
if (xj == xi || x <= ss) {
Intersections++; } } }
// If the number of edges we passed through is odd, then it’s in the polygon.
if (intersections % 2 != 0) {
return true;
} else {
return false;
}