检查点是否在多边形内部

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

我不想使用第三方解决方案，例如 Google Maps API 或这个 https://github.com/mattwilliamson/Google-Maps-Point-in-Polygon。

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

- user3378649

---

选择一个多边形外的点并检查从该点到您的点的直线是否与定义多边形周长的奇数条线相交。 - Hogan

您可以在此处实时检查代码：我将一个点放在多边形中http://jsfiddle.net/nvNNF/2/，它返回“False”。 - user3378649

请注意 https://en.wikipedia.org/wiki/Point_in_polygon 和 https://en.wikipedia.org/wiki/Complex_polygons 这两个页面的内容。 - Emery Lapinski

第三行末尾的 poly[i].y 应改为 poly[i][1]。此外，该函数检查点是否在多边形内，而非点是否属于多边形。 - Ben

你的for循环没有必要有那么多变量，这会降低可读性。你可以逐个测试每个条件，然后进行警报，在代码结尾之前，将所有条件合并并再次检查。 - almost a beginner

查看相关问题：question - undefined

Answer 1

在Github上有一个项目，其中包含代码：https://github.com/substack/point-in-polygon（MIT许可证）：

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

使用方法：

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

- Aaron Digulla

---

JavaScript使用普通的64位双精度IEEE数字，就像其他任何语言一样。这给了你大约16个数字，应该足够用于坐标。8个数字已经给了你毫米级的精度（https://en.wikipedia.org/wiki/Decimal_degrees）。 - Aaron Digulla

@AaronDigulla 这并不完全正确。在 JavaScript 中尝试这个简单的东西：0.3 - 0.2 并将输出打印到控制台。 - Pedro Silva

让我这样说吧：它要么在C/C++、Java和JavaScript中都有效，要么在这三种语言中都无效。它们都使用完全相同的方法来表示数字。使用编译器并不能赋予编程语言神话般的功能。C/C++和Java库只是在打印结果时更擅长四舍五入而已。 - Aaron Digulla

谢谢，之前运行得很好，但是我刚刚意识到它对于位于多边形边缘或角落的点给出了混合结果...如何编辑才能让它始终将这些点视为内部？ - treeseal7

如果您将多边形的坐标传递给此函数以检查它们是否在内部，则其中一半会返回true。 - Alexander Pravdin

Answer 2

您的多边形数组看起来像GeoJSON多边形结构中的coordinates数组（请阅读更多信息：https://macwright.org/2015/03/23/geojson-second-bite.html和http://geojson.org）。因此，您可以使用处理geoJSON数据的库。请查看Is it possible to determine if a GeoJSON point is inside a GeoJSON polygon using JavasScript?问题中的答案和评论。

简而言之，我被turf (https://github.com/turfjs/turf)救了。 还有d3 (https://github.com/d3/d3-geo#geoContains)，但我在使用它时遇到了问题。

更新： 当点位于多边形的“边缘”上时，我注意到turf会提供不一致的结果。我已创建了问题，并正在等待开发人员的回答。

更新2： 通过使用最新版本的turf（我使用的是4.6.1而不是3.0.14），“边界点”问题得到解决。现在一切都好了。

- surfrider

Answer 3

这是我最终成功得到的函数。我通过从这里采用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是测试点的纬度和经度。

- Mark Okhman

---

谢谢！非常好用。我能够适应这个。返回值要么是false，0或1。我将其更改为var oddNodes = 0并返回oddNodes == 1以获得最终布尔值。 - Turbo

它对我没有用。无论点在内部还是外部，我总是得到1。请帮帮我。 - Krishna

这个不起作用；无论如何，是否存在一个开源函数来填充颜色区域？如果有的话，只需要将所有填充点与指定坐标进行比较，对于复杂的多边形更可靠。 - jumpjack

Answer 4

在我的情况下，我做了以下的事情，这样就可以正常工作了：最初的回答。

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

- Renish Gotecha

---

我在我的解决方案中尝试了它，代码并不适用于所有情况，很多时候它会返回在多边形外部的点为真的结果。 - manaschopra98

Answer 5

我对Aaron的答案中的函数进行了现代化更新：

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
}

- justdvl