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

Question

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

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

Answer 1

如果四边形是凸的，则可以使用此算法：

短版：对于每条扫描线（水平位图线），找到与该扫描线相交的边缘，并复制它们之间的像素。

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

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

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