How to check whether point lies inside/outside the Polygon

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.

Polygon

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.”

Ray Casting algorithm
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;

}

Related Posts

Leave a comment