问题说明：我有一个矩形且均匀间隔的像素图像，其顶点坐标为 (i,j), (i+1,j), (i, j+1), (i+1, j+1) [i= 0,...,m-1; j=0,...,n-1] 和具有顶点坐标 (x_1,y_1), ..., (x_n, y_n) 的多边形 P。现在我想有效地计算每个像素与 P 重叠的百分比。P 可以是非凸的，甚至是自相交的。
本质上，这是扫描线光栅化算法的“软”概括，可以有效地检查像素中心是否位于多边形内部/外部。
我可以想到以下方法：
(1) 对图像进行上采样（例如，10*10 倍），计算多边形内有多少个子像素中心，然后除以 100。问题：时间效率、内存效率、准确性。
(2) 使用扫描线算法在稍大的 (0.5,0.5) 平移网格上计算完全位于内部/外部的像素，创建“边界”像素列表，沿边缘逆时针行走，然后计算沿途所有像素的交叉区域。问题：需要微妙的编码，容易引入错误。
我的问题：有没有人遇到过这个问题，你知道第三种更好的方法吗？如果没有，您是否在 (1) 或 (2) 方面获得了更好的体验？我认为这个问题可能出现在抗锯齿的背景下？
进行精确的几何分析可能不会太困难。
首先处理那些被多边形部分覆盖的像素：您可以使用光线追踪技术快速找到与多边形边缘相交的所有像素。然后，您可以使用Cohen-Sutherland算法有效地找到边缘和像素之间的交点，因此您可以计算该像素的覆盖区域。
请注意，您可以避免 Cohen-Sutherland 中涉及的两个裁剪操作之一，因为相邻像素将共享一个线段交点。例如 - 如果您有两个相邻的像素，A并且在点、和B处与线段相交，那么和将是相同的。剪辑时将片段传递到例程中应避免重复工作。p->qa1a2b1b2a2b1a2->qB
您必须特别处理包含多边形顶点的像素，但这也不应该太棘手：Cohen-Sutherland 也会在这里提供帮助。
自相交的多边形也会抛出一些特殊情况来处理 - 与两个或多个边缘相交的像素。我可以很容易地想象，在所有情况下准确处理这些可能会变得很棘手，所以我很想在这里做上采样方法。
一旦确定了这些边缘像素，您就可以执行标准扫描线来填充多边形的内部像素。
编辑：实际上，现在我想多了，你可以完全跳过 Cohen-Sutherland 步骤。链接论文中的算法可以很容易地扩展为返回片段和像素网格之间的交点。该段将在 处留下一个给定的像素min( tMaxX, tMaxY )。跟踪最后一个出口点以重新用作下一个像素的入口点。
我会做
1a）当像素部分重叠时上采样：
但不是整个图像，只有要检查的当前像素，或者当前扫描线中的所有像素（如果有帮助的话）。
比没有内存参数。
速度？高达 16x16 我认为速度不是问题。