像素与多边形重叠：高效（扫描线类型）算法

Question

问题说明： 我有一个由像素组成的矩形且像素间等距，每个像素具有顶点坐标 (i,j), (i+1,j), (i, j+1), (i+1, j+1) [i=0,...,m-1; j=0,...,n-1]，以及一个多边形 P，其顶点坐标为 (x_1,y_1), ..., (x_n, y_n)。现在我想要高效地计算每个像素与 P 的重叠百分比。P 可能是非凸多边形，甚至可能存在自交。

本质上，这是“软件”扫描线栅格化算法的一般化，可以有效地检查像素中心是否位于多边形内部/外部。

我可以考虑以下方法： （1）将图像上采样（例如按因子10*10），统计多少个子像素中心位于多边形内，并除以100。问题：时间效率、内存效率、精度。 （2）在略大且由（0.5,0.5）平移的网格上使用扫描线算法来计算完全位于内部/外部的像素，创建“边界线”像素列表，在边缘逆时针行走并计算与沿途所有像素的相交区域。问题：需要细致编码，容易引入错误。

我的问题：是否已有人遇到此问题，您知道第三种更优秀的方法吗？如果没有，您是通过（1）还是（2）获得更好的体验？我假设这个问题可能在抗锯齿的情况下出现。

- Frederik Kaster

---

有进展吗？我正在处理完全相同的问题。 - nimcap

Answer 1

做准确的几何分析可能并不太困难。首先处理那些被多边形部分覆盖的像素：你可以使用 射线跟踪技术 快速找到所有与多边形边相交的像素。然后，你可以使用 Cohen-Sutherland 算法高效地找到边和像素的交点，从而计算出该像素的覆盖面积。请注意，你可以避免 Cohen-Sutherland 中涉及的两个剪切操作中的一个，因为相邻像素将共享一个段交点。例如-如果你有两个相邻的像素 A 和 B，在点 a1、a2、b1 和 b2 处与线段 p->q 相交，则 a2 和 b1 将是相同的。当对 B 进行剪切时，将段 a2->q 传递到例程中应避免重复工作。

你需要特别处理包含多边形顶点的像素，但这应该不会太麻烦：Cohen-Sutherland算法同样可以帮助解决。

自相交多边形也会引起一些特殊情况 - 与两条或更多边缘相交的像素。我可以想象在所有情况下准确处理这些可能会变得棘手，因此我倾向于在这里使用上采样方法。

一旦识别出这些边缘像素，您可以执行标准的扫描线操作来填充多边形的内部像素。

编辑：实际上，现在我再考虑一下，你完全可以跳过Cohen-Sutherland步骤。链接论文中的算法可以轻松扩展为返回分段和像素网格之间的交点。段将在min( tMaxX, tMaxY )处离开给定像素。跟踪最后一个退出点以便重复用作下一个像素的入口点。

- ryanm

Answer 2

我会这样做

1a) 当像素部分重叠时上采样：

但不是整个图像，只有当前要检查的像素，或者如果有帮助的话，当前扫描线上的所有像素。

那么就没有内存参数的问题了。

速度？最高达16x16，我认为速度不是问题。

- AlexWien

---

有点取巧，但我猜应该能行。我只担心当我们单独处理每个（边缘）像素时，扫描线算法的效率会大幅下降。 - Frederik Kaster