一个高效的算法是什么，可以复制在四边形内的像素？

Question

4

我有两个位图，我想在一个由四个顶点（四边形）定义的区域内仅将像素从A复制到B。位图A和B具有相同的大小，并且四边形被定义为图像的像素空间中的四个{x，y}坐标。

最坏的情况是，我可以将每个像素的中心测试与四边形进行比较，以查看像素的中心是否在四边形内，但这非常慢。有更好的算法吗？

- kevin42

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- interjay · Accepted Answer

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

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

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

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

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