迭代多边形中的每个点

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] 
]; 

这将定义一个多边形像这样：

其中每个绿根据上面的顶点，点是我想要迭代的一个点。顶点沿着多边形边缘走向的方向没有任何图案，它可以围绕多边形顺时针或逆时针旋转。但是，他们会处于有序状态;也就是说，如果您放下笔并按顺序移动到每个顶点，而不抬起，并且它将绘制轮廓而不跨越多边形。

用例是我从通过画布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检查来解决，这会使该解决方案比我想要的要重得多。

EDIT
迭代的整个图像中的每个像素和施加PointInPoly检查每个也是不可接受的;它会比上面的算法更慢。

Answer 1

如果您的多边形是凸的，你可以做到以下几点：

• 的多边形表示里面一侧，一面外的每个边缘创建一个行（这是基于正常的，它可以是取决于卷绕方向）
• 对于已经计算的边界框内的每个像素，检查像素是否在线的内侧。如果像素位于任何线条的外侧，则它位于多边形之外。如果它在里面，那么它就在里面。

的基本算法就是从这里开始：https://github.com/thegrandpoobah/voronoi/blob/master/stippler/stippler.cpp#L187

如果你的多边形不凸的，那么我会做的是实际绘制在已知的色彩在画布上的多边形，然后应用iterative flood fill algorithm。这就要求你至少知道一个像素位于内部，但这不应该是一个昂贵的测试。但是如果你不能在屏幕外的缓冲区（不熟悉canvas标签）做到这一点，那么这可能不适用于JavaScript。