1

假设我在网格环境中有某个多边形的顶点，我如何遍历它包含的每个单元格（包括边缘上的单元格）？

为了澄清，我有以下顶点（算作左上角是(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]
];

这将定义一个多边形，例如：

网格

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

用例是我imageData通过画布 API 加载了来自 PNG 的文件。这个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检查也是不可接受的；它甚至比上述算法还要慢。

4

1 回答 1

1

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

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

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

如果您的多边形不是凸面的，那么我要做的就是在画布上以已知颜色实际绘制多边形，然后应用迭代洪水填充算法。这要求您至少知道内部的一个像素，但这不应该是一项昂贵的测试。但是，如果您不能在屏幕外缓冲区（不熟悉画布标签）中执行此操作，这可能不适合 JavaScript。

于 2012-11-15T06:29:31.283 回答