Javascript：多边形中的点性能改进
Javascript: point-in-polygon performance improvement
我有一组对象。每个对象代表一个点，具有一个 ID 和一个具有 x y 坐标的数组。 , 例如:
let points = [{id: 1, coords: [1,2]}, {id: 2, coords: [2,3]}]
我还有一个包含 x y 坐标的数组。这个数组代表一个多边形，例如：
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 毫秒为每个点调用 pointInPolygon 函数会使整个过程非常缓慢。
我正在寻找一种更快的方法来完成此任务。例如：也许，当鼠标绘制多边形时，我们可以查找一些离鼠标位置最近的点并将其存储在 closestPoints 数组中，而不是每 100 毫秒触发一次此函数。然后，当鼠标 x/y 得到 higher/lower 超过某个值时，它只会循环遍历 closestPoints 中的点和多边形中已经存在的点。但我不知道这些 closestPoints 会是什么，或者整个方法是否有意义。但我确实觉得解决方案是减少我们每次必须循环的点数。
需要说明的是，我项目中的 4000 多个点是固定的——它们不是动态生成的，但始终具有完全相同的坐标。事实上，这些点代表多边形的质心，代表地图上城市的边界。因此，例如，可以提前为每个点计算 closestPoints（在这种情况下，我们将针对这些点进行计算，而不是像上一段中那样计算鼠标位置）。
有计算几何专家可以帮助我吗？
如果我没理解错的话，从鼠标记录的新点将使多边形变大一个点。因此，如果在某个时刻多边形由 n 点 (0,1,...,n-1) 和一个新点定义p 被记录，然后多边形变成 (0,1,...,n-1,p).
所以这意味着从多边形中删除了一条边，并添加了两条边。
例如，假设我们在多边形上有 9 个点，编号为 0 到 8，其中点 8 是添加到它的最后一个点：
灰线是闭合多边形的边。
现在鼠标移动到点9，添加到多边形：
从多边形中删除了灰色边，并添加了两条绿色边。现在遵守以下规则：
由灰色和两条绿色边形成的三角形中的点与更改前的位置相比交换了多边形的 in/out。所有其他点保留其先前的 in/out 状态。
所以，如果你想在内存中保留每个点的状态，那么你只需要检查每个点是否在上面提到的三角形内，如果是，你需要切换那个点的状态.
由于测试是否包含在三角形中比测试可能复杂的多边形所花费的时间更少，因此这将导致更有效的算法。
可以进一步提高效率，如果取角点在(x0,y0的三角形的外接矩形),(x1,y0),(x1,y 1),(x0, y1)。那么您已经可以跳过 x 或 y 坐标超出范围的点：
蓝色框外的任何点都不会改变状态：如果在添加最后一个点 9 之前它在多边形内部，那么现在它仍然是。仅对于框内的点，您需要进行 pointInPolygon 测试， 但仅针对三角形，而不是整个多边形 。如果那个测试returnstrue，那么测试点的状态必须被切换。
在方框中分组点
为了进一步加快这个过程，您可以将带有网格的平面划分为方形框，其中每个点属于一个框，但一个框通常会有很多点。为了确定哪些点在三角形中，您可以首先确定哪些框与三角形重叠。
为此，您不必测试每个框，但可以从三角形边缘的坐标中导出框。
那么只需要对剩下的方框内的点进行单独测试即可。您可以调整盒子大小，看看它如何影响性能。
这是一个工作示例，实现了这些想法。有10000分了，但是我的电脑没有卡顿:
canvas.width = document.body.clientWidth;
const min = [0, 0],
max = [canvas.width, canvas.height],
points = Array.from(Array(10000), i => {
let x = Math.floor(Math.random() * (max[0]-min[0]) + min[0]);
let y = Math.floor(Math.random() * (max[1]-min[1]) + min[1]);
return [x, y];
}),
polygon = [],
boxSize = Math.ceil((max[0] - min[0]) / 50),
boxes = (function (xBoxes, yBoxes) {
return Array.from(Array(yBoxes), _ =>
Array.from(Array(xBoxes), _ => []));
})(toBox(0, max[0])+1, toBox(1, max[1])+1),
insidePoints = new Set,
ctx = canvas.getContext('2d');
function drawPoint(p) {
ctx.fillRect(p[0], p[1], 1, 1);
}
function drawPolygon(pol) {
ctx.beginPath();
ctx.moveTo(pol[0][0], pol[0][1]);
for (const p of pol) {
ctx.lineTo(p[0], p[1]);
}
ctx.stroke();
}
function segmentMap(a, b, dim, coord) {
// Find the coordinate where ab is intersected by a coaxial line at
// the given coord.
// First some boundary conditions:
const dim2 = 1 - dim;
if (a[dim] === coord) {
if (b[dim] === coord) return [a[dim2], b[dim2]];
return [a[dim2]];
}
if (b[dim] === coord) return [b[dim2]];
// See if there is no intersection:
if ((coord > a[dim]) === (coord > b[dim])) return [];
// There is an intersection point:
const res = (coord - a[dim]) * (b[dim2] - a[dim2]) / (b[dim] - a[dim]) + a[dim2];
return [res];
}
function isLeft(a, b, c) {
// Return true if c lies at the left of ab:
return (b[0] - a[0])*(c[1] - a[1]) - (b[1] - a[1])*(c[0] - a[0]) > 0;
}
function inTriangle(a, b, c, p) {
// First do a bounding box check:
if (p[0] < Math.min(a[0], b[0], c[0]) ||
p[0] > Math.max(a[0], b[0], c[0]) ||
p[1] < Math.min(a[1], b[1], c[1]) ||
p[1] > Math.max(a[1], b[1], c[1])) return false;
// Then check that the point is on the same side of each of the
// three edges:
const x = isLeft(a, b, p),
y = isLeft(b, c, p),
z = isLeft(c, a, p);
return x ? y && z : !y && !z;
}
function toBox(dim, coord) {
return Math.floor((coord - min[dim]) / boxSize);
}
function toWorld(dim, box) {
return box * boxSize + min[dim];
}
function drawBox(boxX, boxY) {
let x = toWorld(0, boxX);
let y = toWorld(1, boxY);
drawPolygon([[x, y], [x + boxSize, y], [x + boxSize, y + boxSize], [x, y + boxSize], [x, y]]);
}
function triangleTest(a, b, c, points, insidePoints) {
const markedBoxes = new Set(), // collection of boxes that overlap with triangle
box = [];
for (let dim = 0; dim < 2; dim++) {
const dim2 = 1-dim,
// Order triangle points by coordinate
[d, e, f] = [a, b, c].sort( (p, q) => p[dim] - q[dim] ),
lastBox = toBox(dim, f[dim]);
for (box[dim] = toBox(dim, d[dim]); box[dim] <= lastBox; box[dim]++) {
// Calculate intersections of the triangle edges with the row/column of boxes
const coord = toWorld(dim, box[dim]),
intersections =
[...new Set([...segmentMap(a, b, dim, coord),
...segmentMap(b, c, dim, coord),
...segmentMap(a, c, dim, coord)])];
if (!intersections.length) continue;
intersections.sort( (a,b) => a - b );
const lastBox2 = toBox(dim2, intersections.slice(-1)[0]);
// Mark all boxes between the two intersection points
for (box[dim2] = toBox(dim2, intersections[0]); box[dim2] <= lastBox2; box[dim2]++) {
markedBoxes.add(boxes[box[1]][box[0]]);
if (box[dim]) {
markedBoxes.add(boxes[box[1]-dim][box[0]-(dim2)]);
}
}
}
}
// Perform the triangle test for each individual point in the marked boxes
for (const box of markedBoxes) {
for (const p of box) {
if (inTriangle(a, b, c, p)) {
// Toggle in/out state of this point
if (insidePoints.delete(p)) {
ctx.fillStyle = '#000000';
} else {
ctx.fillStyle = '#e0e0e0';
insidePoints.add(p);
}
drawPoint(p);
}
}
}
}
// Draw points
points.forEach(drawPoint);
// Distribute points into boxes
for (const p of points) {
let hor = Math.floor((p[0] - min[0]) / boxSize);
let ver = Math.floor((p[1] - min[1]) / boxSize);
boxes[ver][hor].push(p);
}
canvas.addEventListener('mousemove', (e) => {
if (e.buttons !== 1) return;
polygon.push([Math.max(e.offsetX,0), Math.max(e.offsetY,0)]);
ctx.strokeStyle = '#000000';
drawPolygon(polygon);
const len = polygon.length;
if (len > 2) {
triangleTest(polygon[0], polygon[len-2+len%2], polygon[len-1-len%2], points, insidePoints);
}
});
canvas.addEventListener('mousedown', (e) => {
// Start a new polygon
polygon.length = 0;
});
Drag mouse to draw a shape:
<canvas id="canvas"></canvas>
每次更新多边形时，保留一张背景图像，在其中执行多边形填充。
然后测试任何点的内部性将花费常数时间，与多边形复杂度无关。
我有一组对象。每个对象代表一个点，具有一个 ID 和一个具有 x y 坐标的数组。 , 例如:
let points = [{id: 1, coords: [1,2]}, {id: 2, coords: [2,3]}]
我还有一个包含 x y 坐标的数组。这个数组代表一个多边形，例如：
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 毫秒为每个点调用 pointInPolygon 函数会使整个过程非常缓慢。
我正在寻找一种更快的方法来完成此任务。例如：也许，当鼠标绘制多边形时，我们可以查找一些离鼠标位置最近的点并将其存储在 closestPoints 数组中，而不是每 100 毫秒触发一次此函数。然后，当鼠标 x/y 得到 higher/lower 超过某个值时，它只会循环遍历 closestPoints 中的点和多边形中已经存在的点。但我不知道这些 closestPoints 会是什么，或者整个方法是否有意义。但我确实觉得解决方案是减少我们每次必须循环的点数。
需要说明的是，我项目中的 4000 多个点是固定的——它们不是动态生成的，但始终具有完全相同的坐标。事实上，这些点代表多边形的质心，代表地图上城市的边界。因此，例如，可以提前为每个点计算 closestPoints（在这种情况下，我们将针对这些点进行计算，而不是像上一段中那样计算鼠标位置）。
有计算几何专家可以帮助我吗？
如果我没理解错的话，从鼠标记录的新点将使多边形变大一个点。因此，如果在某个时刻多边形由 n 点 (0,1,...,n-1) 和一个新点定义p 被记录，然后多边形变成 (0,1,...,n-1,p).
所以这意味着从多边形中删除了一条边，并添加了两条边。
例如，假设我们在多边形上有 9 个点，编号为 0 到 8，其中点 8 是添加到它的最后一个点：
灰线是闭合多边形的边。
现在鼠标移动到点9，添加到多边形：
从多边形中删除了灰色边，并添加了两条绿色边。现在遵守以下规则：
由灰色和两条绿色边形成的三角形中的点与更改前的位置相比交换了多边形的 in/out。所有其他点保留其先前的 in/out 状态。
所以，如果你想在内存中保留每个点的状态，那么你只需要检查每个点是否在上面提到的三角形内，如果是，你需要切换那个点的状态.
由于测试是否包含在三角形中比测试可能复杂的多边形所花费的时间更少，因此这将导致更有效的算法。
可以进一步提高效率，如果取角点在(x0,y0的三角形的外接矩形),(x1,y0),(x1,y 1),(x0, y1)。那么您已经可以跳过 x 或 y 坐标超出范围的点：
蓝色框外的任何点都不会改变状态：如果在添加最后一个点 9 之前它在多边形内部，那么现在它仍然是。仅对于框内的点，您需要进行 pointInPolygon 测试， 但仅针对三角形，而不是整个多边形 。如果那个测试returnstrue，那么测试点的状态必须被切换。
在方框中分组点
为了进一步加快这个过程，您可以将带有网格的平面划分为方形框，其中每个点属于一个框，但一个框通常会有很多点。为了确定哪些点在三角形中，您可以首先确定哪些框与三角形重叠。
为此，您不必测试每个框，但可以从三角形边缘的坐标中导出框。
那么只需要对剩下的方框内的点进行单独测试即可。您可以调整盒子大小，看看它如何影响性能。
这是一个工作示例，实现了这些想法。有10000分了，但是我的电脑没有卡顿:
canvas.width = document.body.clientWidth;
const min = [0, 0],
max = [canvas.width, canvas.height],
points = Array.from(Array(10000), i => {
let x = Math.floor(Math.random() * (max[0]-min[0]) + min[0]);
let y = Math.floor(Math.random() * (max[1]-min[1]) + min[1]);
return [x, y];
}),
polygon = [],
boxSize = Math.ceil((max[0] - min[0]) / 50),
boxes = (function (xBoxes, yBoxes) {
return Array.from(Array(yBoxes), _ =>
Array.from(Array(xBoxes), _ => []));
})(toBox(0, max[0])+1, toBox(1, max[1])+1),
insidePoints = new Set,
ctx = canvas.getContext('2d');
function drawPoint(p) {
ctx.fillRect(p[0], p[1], 1, 1);
}
function drawPolygon(pol) {
ctx.beginPath();
ctx.moveTo(pol[0][0], pol[0][1]);
for (const p of pol) {
ctx.lineTo(p[0], p[1]);
}
ctx.stroke();
}
function segmentMap(a, b, dim, coord) {
// Find the coordinate where ab is intersected by a coaxial line at
// the given coord.
// First some boundary conditions:
const dim2 = 1 - dim;
if (a[dim] === coord) {
if (b[dim] === coord) return [a[dim2], b[dim2]];
return [a[dim2]];
}
if (b[dim] === coord) return [b[dim2]];
// See if there is no intersection:
if ((coord > a[dim]) === (coord > b[dim])) return [];
// There is an intersection point:
const res = (coord - a[dim]) * (b[dim2] - a[dim2]) / (b[dim] - a[dim]) + a[dim2];
return [res];
}
function isLeft(a, b, c) {
// Return true if c lies at the left of ab:
return (b[0] - a[0])*(c[1] - a[1]) - (b[1] - a[1])*(c[0] - a[0]) > 0;
}
function inTriangle(a, b, c, p) {
// First do a bounding box check:
if (p[0] < Math.min(a[0], b[0], c[0]) ||
p[0] > Math.max(a[0], b[0], c[0]) ||
p[1] < Math.min(a[1], b[1], c[1]) ||
p[1] > Math.max(a[1], b[1], c[1])) return false;
// Then check that the point is on the same side of each of the
// three edges:
const x = isLeft(a, b, p),
y = isLeft(b, c, p),
z = isLeft(c, a, p);
return x ? y && z : !y && !z;
}
function toBox(dim, coord) {
return Math.floor((coord - min[dim]) / boxSize);
}
function toWorld(dim, box) {
return box * boxSize + min[dim];
}
function drawBox(boxX, boxY) {
let x = toWorld(0, boxX);
let y = toWorld(1, boxY);
drawPolygon([[x, y], [x + boxSize, y], [x + boxSize, y + boxSize], [x, y + boxSize], [x, y]]);
}
function triangleTest(a, b, c, points, insidePoints) {
const markedBoxes = new Set(), // collection of boxes that overlap with triangle
box = [];
for (let dim = 0; dim < 2; dim++) {
const dim2 = 1-dim,
// Order triangle points by coordinate
[d, e, f] = [a, b, c].sort( (p, q) => p[dim] - q[dim] ),
lastBox = toBox(dim, f[dim]);
for (box[dim] = toBox(dim, d[dim]); box[dim] <= lastBox; box[dim]++) {
// Calculate intersections of the triangle edges with the row/column of boxes
const coord = toWorld(dim, box[dim]),
intersections =
[...new Set([...segmentMap(a, b, dim, coord),
...segmentMap(b, c, dim, coord),
...segmentMap(a, c, dim, coord)])];
if (!intersections.length) continue;
intersections.sort( (a,b) => a - b );
const lastBox2 = toBox(dim2, intersections.slice(-1)[0]);
// Mark all boxes between the two intersection points
for (box[dim2] = toBox(dim2, intersections[0]); box[dim2] <= lastBox2; box[dim2]++) {
markedBoxes.add(boxes[box[1]][box[0]]);
if (box[dim]) {
markedBoxes.add(boxes[box[1]-dim][box[0]-(dim2)]);
}
}
}
}
// Perform the triangle test for each individual point in the marked boxes
for (const box of markedBoxes) {
for (const p of box) {
if (inTriangle(a, b, c, p)) {
// Toggle in/out state of this point
if (insidePoints.delete(p)) {
ctx.fillStyle = '#000000';
} else {
ctx.fillStyle = '#e0e0e0';
insidePoints.add(p);
}
drawPoint(p);
}
}
}
}
// Draw points
points.forEach(drawPoint);
// Distribute points into boxes
for (const p of points) {
let hor = Math.floor((p[0] - min[0]) / boxSize);
let ver = Math.floor((p[1] - min[1]) / boxSize);
boxes[ver][hor].push(p);
}
canvas.addEventListener('mousemove', (e) => {
if (e.buttons !== 1) return;
polygon.push([Math.max(e.offsetX,0), Math.max(e.offsetY,0)]);
ctx.strokeStyle = '#000000';
drawPolygon(polygon);
const len = polygon.length;
if (len > 2) {
triangleTest(polygon[0], polygon[len-2+len%2], polygon[len-1-len%2], points, insidePoints);
}
});
canvas.addEventListener('mousedown', (e) => {
// Start a new polygon
polygon.length = 0;
});
Drag mouse to draw a shape:
<canvas id="canvas"></canvas>
每次更新多边形时，保留一张背景图像，在其中执行多边形填充。
然后测试任何点的内部性将花费常数时间，与多边形复杂度无关。