Check if Point Is Inside A Polygon

Question

I want to check if a point lies within a specific polygon. The polygon is:

 polygon=   [ [-73.89632720118, 40.8515320489962],
              [-73.8964878416508, 40.8512476593594],
              [-73.8968799791431, 40.851375925454],
              [-73.8967188588015, 40.851660158514],
              [-73.89632720118, 40.8515320489962] ]
          

The points I want to check are:

1 = [40.8515320489962,-73.89632720118]
2 = [40.8512476593594,-73.8964878416508]
3 = [40.851375925454,-73.8968799791431]
4 = [40.851660158514,-73.8967188588015]
5 = [40.8515320489962,-73.89632720118]

How can I tell if each of these points lies within this polygon?

The algorithm below does not work. I don't know why.

pt[lat,long]

function isPointInPoly(poly, pt){
    for(var c = false, i = -1, l = poly.length, j = l - 1; ++i < l; j = i)
        ((poly[i][1] <= pt[1] && pt[1] < poly[j][1]) || (poly[j][1] <= pt[1] && pt[1] < poly[i][1]))
        && (pt[0] < (poly[j][0] - poly[i][0]) * (pt[1] - poly[i][1]) / (poly[j][1] - poly[i][1]) + poly[i][0])
        && (c = !c);
    return c;
}

I don't want to use a third party solution such as google maps API or this one https://github.com/mattwilliamson/Google-Maps-Point-in-Polygon.

My attempt is here: http://jsfiddle.net/nvNNF/2/

Churl

Pick a point outside the polygon check and see if a line from that point to your point intersects an odd number of lines that define the perimeter of the polygon. – Aeromancy

You can check the code live here: I put one the point in polygone jsfiddle.net/nvNNF/2 and it returns "False" – Churl

en.wikipedia.org/wiki/Point_in_polygon and be careful of en.wikipedia.org/wiki/Complex_polygons – Milquetoast

poly[i].y should be poly[i][1] at the end of line 3. Also that function checks if the point is inside the polygon not if the point belongs to the polygon. – Dingman

No reason for your for loop to have so many variables, reducing readability. You can test each condition individually and then alert, and once you reach the end of your code, then you combine all your conditions and check again. – Protoactinium

check out this related question – Trondheim

Answer 1

There is a project on Github with code: https://github.com/substack/point-in-polygon (MIT license):

function inside(point, vs) {
    // ray-casting algorithm based on
    // https://wrf.ecse.rpi.edu/Research/Short_Notes/pnpoly.html
    
    var x = point[0], y = point[1];
    
    var inside = false;
    for (var i = 0, j = vs.length - 1; i < vs.length; j = i++) {
        var xi = vs[i][0], yi = vs[i][1];
        var xj = vs[j][0], yj = vs[j][1];
        
        var intersect = ((yi > y) != (yj > y))
            && (x < (xj - xi) * (y - yi) / (yj - yi) + xi);
        if (intersect) inside = !inside;
    }
    
    return inside;
};

Usage:

// array of coordinates of each vertex of the polygon
var polygon = [ [ 1, 1 ], [ 1, 2 ], [ 2, 2 ], [ 2, 1 ] ];
inside([ 1.5, 1.5 ], polygon); // true

The test function is here: https://github.com/substack/point-in-polygon/blob/master/index.js

Note: This code doesn't work reliably when the point is a corner of the polygon or on an edge. There is an improved version here: https://github.com/mikolalysenko/robust-point-in-polygon

Sirkin

I think it is OK to copy and paste a code given that you have included the reference. It will give the credit to the original author. – Frost

@ChathurangaChandrasekara: I know that it's not allowed by law. Giving credit isn't enough to satisfy copyright laws. – Sirkin

@markkillah Correct. The code above is for euclidean space. You need to transform the coordinates first or use an algorithm that can handle polar/non-euclidean geometry. – Sirkin

I think this doesn't work for coordinates because of javascript precision. – Litigable

@PedroSilva JavaScript uses normal 64bit double precision IEEE numbers just like any other language. That gives you about 16 digits which should be enough for coordinates. 8 digits already give you millimeter precision (en.wikipedia.org/wiki/Decimal_degrees) – Sirkin

@AaronDigulla thats not completly true. try this simple thing in javascript: 0,3 - 0,2 and console.log the output – Litigable

@PedroSilva Let me put it this way: It either works in C/C++, Java and JavaScript or it works for none of the three. They all use the exact same method to represent numbers. Using a compiler doesn't give programming languages mythical features. The C/C++ and Java libraries are just a little better at rounding the result when they print it. – Sirkin

thanks, was working great, but just realised that it gives mixed results for points that lie on the edges or corners of the polygon... how could it be edited to accept these as always inside? – Whiteman

If you will pass polygon's coordinates to this function to check are they inside itself, you will get true on half of them. – Cytotaxonomy

@wawmsey I'm not sure. I would start with the comparisons in the var intersect expression. Some of them should probably include equality, maybe all of them. – Sirkin

is it possible to get index of which is sent true value? – Misconduct

@Adnanhaider The question doesn't make sense in a mathematical way. Either you're inside or you're not. If you're inside, then you're on "inside" of all vertices which make up the polygon. They are all the same in this respect. – Sirkin

@AaronDigulla my question was i have list of list of polygon i want to check it that which index is i click inside it, – Misconduct

@Adnanhaider Ah, sorry, missed that. Loop over all polygons outside this function. I don't know if there is a way to check all polygons at once; the only optimization that I can think of would be a bounding box over all polygons: If the point is outside, you can skip the tests. – Sirkin

Note that this ONLY works if the polygon points array is in a sequential order (clockwise or anti-clockwise). I was stuck at implementing this for that reason when I used three.js position buffer attribute – Trondheim

I am looking at the code in github.com/mikolalysenko/robust-point-in-polygon but I need some help in finding the code being referenced in the following: var orient = require('robust-orientation') – Presumptuous

Answer 2

Your polygon array looks like coordinates array in GeoJSON polygon structure (read more at https://macwright.org/2015/03/23/geojson-second-bite.html and http://geojson.org). So maybe you can use libraries which are working with geoJSON data? Look at answer and comments to OP in Is it possible to determine if a GeoJSON point is inside a GeoJSON polygon using JavasScript?

In short, my day was saved by turf (https://github.com/turfjs/turf) There is also d3 (https://github.com/d3/d3-geo#geoContains) but i had issues with it.

UPD: I noticed turf is giving inconsistent results when point is on 'edge' of polygon. I created issue and i am waiting for answer from developers.

UPD2: 'Boundary points' issue is resolved by using latest version of turf (i used 3.0.14 instead of 4.6.1). It's all right now.

Sipple

Answer 3

Here is the function I finally got working. I got it by adopting C code to javascript from here (with explanation).

function checkcheck (x, y, cornersX, cornersY) {

    var i, j=cornersX.length-1 ;
    var odd = false;

    var pX = cornersX;
    var pY = cornersY;

    for (i=0; i<cornersX.length; i++) {
        if ((pY[i]< y && pY[j]>=y ||  pY[j]< y && pY[i]>=y)
            && (pX[i]<=x || pX[j]<=x)) {
              odd ^= (pX[i] + (y-pY[i])*(pX[j]-pX[i])/(pY[j]-pY[i])) < x; 
        }

        j=i; 
    }

return odd;
}

Where cornersX = array with x or latitude vertices array, cornersY = array with y or longitude array. X, Y - latitude and longitude of tested point.

Syd

Thanks! Works great. I was able to adapt this. The return values are either false, 0, or 1. I changed to var oddNodes = 0 and return oddNodes == 1 to have a final boolean. – Horseshoe

It's not working for me. I am always getting 1. whatever point is inside or outside. Please help me. – Posthaste

this does not work; anyway, does it exist an opensource function to fill an area with a color? If it does, it would be just a matter of comparing all filled points to specified coordinates, much more reliable for complex polygons. – Halland

Answer 4

In my case i did following thing it's working fine for me

function isLatLngInZone(latLngs,lat,lng){
  // latlngs = [{"lat":22.281610498720003,"lng":70.77577162868579},{"lat":22.28065743343672,"lng":70.77624369747241},{"lat":22.280860953131217,"lng":70.77672113067706},{"lat":22.281863655593973,"lng":70.7762061465462}];
  vertices_y = new Array();
  vertices_x = new Array();
  longitude_x = lng;
  latitude_y = lat;
  latLngs = JSON.parse(latLngs);
  var r = 0;
  var i = 0;
  var j = 0;
  var c = 0;
  var point = 0;

  for(r=0; r<latLngs.length; r++){
   vertices_y.push(latLngs[r].lat);
   vertices_x.push(latLngs[r].lng);
  }
  points_polygon = vertices_x.length;
  for(i = 0, j = points_polygon; i < points_polygon; j = i++){
   point = i;
   if(point == points_polygon)
    point = 0;
   if ( ((vertices_y[point]  >  latitude_y != (vertices_y[j] > latitude_y)) && (longitude_x < (vertices_x[j] - vertices_x[point]) * (latitude_y - vertices_y[point]) / (vertices_y[j] - vertices_y[point]) + vertices_x[point]) ) )
    c = !c;
  }
return c;
}

Subway

I tried it in my solution, the code does not work in all cases, many times it returns true for points lying outside the polygon. – Brimful

Answer 5

I modernised the function from Aaron's answer:

const getIsPointInsidePolygon = (point: number[], vertices: number[][]) => {
const x = point[0]
const y = point[1]

let inside = false
for (let i = 0, j = vertices.length - 1; i < vertices.length; j = i++) {
  const xi = vertices[i][0],
    yi = vertices[i][1]
  const xj = vertices[j][0],
    yj = vertices[j][1]

  const intersect = yi > y != yj > y && x < ((xj - xi) * (y - yi)) / (yj - yi) + xi
  if (intersect) inside = !inside
}

return inside
}

Resa