Javascript:多边形中的点性能改进

Question

我有一个对象数组。每个对象代表一个点，具有一个 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 函数使得整个过程非常缓慢。

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

需要说明的是，我项目中的 4000 多个点是固定的——它们不是动态生成的，但始终具有完全相同的坐标。事实上，这些点代表多边形的质心，代表 map 上城市的边界。因此，例如，可以提前为每个点计算 closestPoints(在这种情况下，我们将针对这些点进行计算，而不是像上一段中那样计算鼠标位置)。

有计算几何专家可以帮助我解决这个问题吗？

Answer 1

如果我没理解错的话，从鼠标记录的新点将使多边形变大一个点。因此，如果在某个时刻多边形由 n 个点 (0,1,...,n-1) 和一个新点 p 定义em> 被记录，然后多边形变为 (0,1,...,n-1,p)。

所以这意味着从多边形中删除了一条边，而是添加了两条边。

例如，假设我们在多边形上有 9 个点，编号为 0 到 8，其中点 8 是添加到它的最后一个点:

灰线是闭合多边形的边。

现在鼠标移动到点 9，它被添加到多边形中:

从多边形中移除灰色边，并添加两条绿色边。现在遵守以下规则:

与更改前的位置相比，由灰色和两条绿色边形成的三 Angular 形中的点在多边形中换入/换出。所有其他点保留其之前的进/出状态。

所以，如果你想在内存中保留每个点的状态，那么你只需要检查每个点是否在上面提到的三 Angular 形内，如果是，你需要切换那个点的状态。

由于测试是否包含在三 Angular 形中比测试可能复杂的多边形花费的时间更少，因此这将导致更有效的算法。

可以进一步提高效率，如果取 Angular 点在(x₀, y₀),(x< sub>1, y₀),(x₁, y₁),(x₀>, y₁)。然后您已经可以跳过具有超出范围的 x 或 y 坐标的点:

蓝色框外的任何点都不会改变状态:如果在添加最后一个点 9 之前它在多边形内部，那么现在它仍然是。仅对于方框内的点，您需要执行 pointInPolygon 测试，但仅针对三 Angular 形，而不是整个多边形。如果该测试返回 true，则必须切换测试点的状态。

方框中的组点

为了进一步加快该过程，您可以使用网格将平面划分为方形框，其中每个点属于一个框，但一个框通常会有很多点。为了确定哪些点在三 Angular 形中，您可以首先确定哪些框与三 Angular 形重叠。

为此，您不必测试每个框，但可以从三 Angular 形边缘上的坐标导出框。

然后只需要单独测试剩余框中的点。您可以调整盒子大小，看看它如何影响性能。

这是一个工作示例，实现了这些想法。有 10000 点，但我的 PC 上没有滞后:

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>