问题说明:
我有一个由像素组成的矩形且像素间等距,每个像素具有顶点坐标 (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)获得更好的体验?我假设这个问题可能在抗锯齿的情况下出现。
本质上,这是“软件”扫描线栅格化算法的一般化,可以有效地检查像素中心是否位于多边形内部/外部。
我可以考虑以下方法: (1)将图像上采样(例如按因子10*10),统计多少个子像素中心位于多边形内,并除以100。问题:时间效率、内存效率、精度。 (2)在略大且由(0.5,0.5)平移的网格上使用扫描线算法来计算完全位于内部/外部的像素,创建“边界线”像素列表,在边缘逆时针行走并计算与沿途所有像素的相交区域。问题:需要细致编码,容易引入错误。
我的问题:是否已有人遇到此问题,您知道第三种更优秀的方法吗?如果没有,您是通过(1)还是(2)获得更好的体验?我假设这个问题可能在抗锯齿的情况下出现。