algorithm - 复制四边形内像素的有效算法是什么？

Question

我有两个位图，只有当像素位于由四个角(四边形)定义的区域内时，我才想将像素从 A 复制到 B。位图 A 和 B 大小相同，四边形定义为图像像素空间中的四个 {x,y} 坐标。

最坏的情况我可以针对四边形测试每个像素的中心以查看像素的中心是否在四边形内，但这非常慢。什么是更好的算法？

Answer 1

如果四边形是凸的，可以用这个算法:

简化版:对于每条扫描线(水平位图线)，找到与该扫描线相交的边，并复制它们之间的像素。

长版:逐行扫描。从顶部顶点(最小 y)开始，并跟踪左侧和右侧的边缘。对于每个 y 值，计算两条边的 x 值(直接使用线方程，或使用 Bresenham's algorithm )。然后将 (xLeft,y) 到 (xRight,y) 处的像素复制到第二个位图中。

当您到达边末端的顶点时，切换到连接到该顶点的另一条边。继续这个直到到达底部顶点。

对于凹四边形，这就更复杂了。您可以使用类似的算法，但对于某些扫描线，将有四个边与扫描线相交。在这种情况下，您需要复制边缘 #1 到 #2 和 #3 到 #4 之间的像素(边缘按 x 值排序)。另一种选择是将四边形分成两个三角形，并对它们使用上述算法。