javascript - 迭代多边形内的每个点

Question

假设我在网格环境中有某个多边形的顶点，我如何迭代它包含的每个单元格(包括边缘上的单元格)？

为了澄清，我有以下顶点(按照左上角为 (0, 0) 的方式进行计数):

//each point is [x, y]
var verts = [
    [1, 1],
    [3, 1],
    [3, 2],
    [4, 2],
    [4, 4],
    [0, 4],
    [0, 3],
    [1, 3]
];

这将定义一个像这样的多边形:

每个绿点都是我想要根据上面的顶点进行迭代的点。顶点沿着多边形边缘行走的方向没有模式，它可以绕多边形顺时针或逆时针行走。然而，它们将会井然有序；也就是说，如果你放下笔，按顺序移动到每个顶点，而不抬起，它就会绘制出轮廓，而不会穿过多边形内部。

用例是我通过 Canvas API 加载了 PNG 的 imageData。这个PNG被分成“区域”，我需要迭代当前“区域”的每个像素。每个“区域”都由一个顶点数组定义，如上所示。

我尝试了类似下面的方法，这将创建一个正方形来迭代数组中每组 4 个顶点。

for(var v = 0, vl = verts.length - 4; v < vl; ++v) {
    //grabbing the minimum X, Y and maximum X, Y to define a square to iterate in
    var minX = Math.min(verts[v][0], verts[v + 1][0], verts[v + 2][0], verts[v + 3][0]),
        minY = Math.min(verts[v][1], verts[v + 1][1], verts[v + 2][1], verts[v + 3][1]),
        maxX = Math.max(verts[v][0], verts[v + 1][0], verts[v + 2][0], verts[v + 3][0]),
        maxY = Math.min(verts[v][1], verts[v + 1][1], verts[v + 2][1], verts[v + 3][1]);

    for(var x = minX; x < maxX; ++x) {
        for(var y = minY; y < maxY; ++y) {
            //do my checks on this pixel located at X, Y in the PNG
        }
    }
}

但是有两个大问题:

1. 它可以重复多边形内的点，并且
2. 它可以抓取多边形之外的点

我可以通过跟踪我检查的点来解决第一个问题，所以我不会重复检查。第二个问题只能通过对每个点运行 PointInPoly 检查来解决，这将使这个解决方案比我想要的要重得多。

编辑
迭代整个图像中的每个像素并对每个像素应用 PointInPoly 检查也是 Not Acceptable ；它会比上面的算法更慢。

Answer 1

如果您的多边形是凸多边形，您可以执行以下操作:

• 为多边形的每条边创建一条线，表示一侧在内侧，一侧在外侧(这是基于法线，法线可能取决于缠绕方向)
• 对于已计算的边界框内的每个像素，检查该像素是否在线的内侧。如果像素位于任何一条线的外侧，则它位于多边形之外。如果它在所有这些里面，那么它就在里面。

基本算法来自这里:https://github.com/thegrandpoobah/voronoi/blob/master/stippler/stippler.cpp#L187

如果您的多边形不是凸的，那么我要做的是以已知颜色在 Canvas 上实际绘制多边形，然后应用 iterative flood fill algorithm 。这要求您至少知道内部的一个像素，但这不应该是一项昂贵的测试。但是，如果您无法在屏幕外缓冲区中执行此操作(不熟悉 canvas 标记)，则这可能不适合 JavaScript。