Javascript:多边形点对点性能改进

Question

我有一系列的对象。每个表示点的对象都有一个ID和一个具有x坐标的数组。，例如：

let points = [{id: 1, coords: [1,2]}, {id: 2, coords: [2,3]}]

我还拥有一个数组，其中包含x坐标。这个数组表示一个多边形，例如：

let polygon = [[0,0], [0,3], [1,4], [0,2]]

多边形被关闭，因此数组的最后一点被链接到第一个点。

我使用以下算法检查多边形内是否有一个点：

pointInPolygon = function (point, polygon) {
  // from https://github.com/substack/point-in-polygon
  let x = point.coords[0]
  let y = point.coords[1]
  let inside = false

  for (let i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {
    let xi = polygon[i][0]
    let yi = polygon[i][1]
    let xj = polygon[j][0]
    let yj = polygon[j][1]
    let intersect = ((yi > y) !== (yj > y)) &&
                    (x < (xj - xi) * (y - yi) / (yj - yi) + xi)
    if (intersect) inside = !inside
  }

  return inside
}

用户用鼠标绘制多边形，其工作方式如下：http://bl.ocks.org/bycoffe/5575904

每次鼠标移动(获得新的坐标)时，我们都必须将鼠标当前的位置添加到多边形中，然后循环遍历所有的点，并在每次迭代时调用点上的pointInPolygon函数。为了提高性能，我已经节流了这个活动：

handleCurrentMouseLocation = throttle(function (mouseLocation, points, polygon) {
    let pointIDsInPolygon = []
    polygon.push(mouseLocation)

    for (let point in points) {
        if (pointInPolygon(point, polygon) {
            pointIDsInPolygon.push(point.id)
        }
    }
    return pointIDsInPolygon
}, 100)

如果点数不是很高(<200)，但是在我当前的项目中，我们已经超过4000分，这是很好的。迭代所有这些点，并每100 ms对每个点调用pointInPolygon函数，这使得整个过程非常滞后。

我正在寻找一种更快的方法来完成这一任务。例如:也许，在鼠标绘制多边形时，我们可以查找离鼠标位置最近的一些点，并将其存储在closestPoints数组中，而不是每100 ms触发一次这个函数。然后，当鼠标x/y比某个值高/低时，它只会循环遍历closestPoints中的点和多边形中已经存在的点。但我不知道这些closestPoints会是什么，或者这整个方法是否有意义。但我确实觉得解决办法是减少我们每次必须循环通过的点数。

要明确的是，我的项目中的4000多个点是固定的-它们不是动态生成的，但是总是有完全相同的坐标。事实上，这些点代表多边形的中心，在地图上代表城市的边界。因此，例如，提前计算每个点的closestPoints是可能的(在本例中，我们计算的是点，而不是像上一段那样的鼠标位置)。

任何能帮我解决这个问题的计算几何专家？

Answer 1

每次更新多边形时，都要保留一个执行多边形填充的背景图像。

然后，测试任何点的内部性质将花费恒定的时间，不依赖于多边形的复杂性。