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/

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/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

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.