检查点是否在多边形内

Question

我想检查一个点是否位于特定的多边形内.多边形是:

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

我要检查的要点是:

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]

如何判断每个点是否在此多边形内？

此算法无效.我不知道为什么.

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].y))
        && (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;
}

我不想使用第三方解决方案,例如谷歌地图API或这一个https://github.com/mattwilliamson/Google-Maps-Point-in-Polygon.

我的尝试在这里:http: //jsfiddle.net/nvNNF/2/

Answer 1

Github上有一个项目代码:https://github.com/substack/point-in-polygon(麻省理工学院许可证):

function inside(point, vs) {
    // ray-casting algorithm based on
    // http://www.ecse.rpi.edu/Homepages/wrf/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;
};

用法:

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

测试功能在这里:https://github.com/substack/point-in-polygon/blob/master/index.js

注意:当点是多边形的一角或边缘时,此代码无法可靠地工作.这里有一个改进的版本:https://github.com/mikolalysenko/robust-point-in-polygon

Answer 2

这是我最终工作的功能.我从这里采用C代码到javascript得到它(有解释).

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;
}

其中cornersX=具有x或纬度顶点数组的数组,cornersY=具有y或经度数组的数组.X,Y - 测试点的经度和纬度.

Answer 3

您的多边形数组看起来像coordinatesGeoJSON多边形结构中的数组(详情请参阅https://macwright.org/2015/03/23/geojson-second-bite.html和http://geojson.org).那么也许您可以使用使用geoJSON数据的库？查看对OP的回答和评论是否可以使用JavasScript确定GeoJSON点是否在GeoJSON多边形内部？

简而言之,我的日子被保存turf(https://github.com/turfjs/turf)还有d3(https://github.com/d3/d3-geo#geoContains),但我遇到了问题.

UPD:我注意到turf当点在多边形的"边缘"上时会产生不一致的结果.我创建了问题,我正在等待开发人员的回答.

UPD2:'边界点'问题通过使用最新版本turf(我使用3.0.14而不是4.6.1)解决.现在好了.