我有两个位图,我想在一个由四个顶点(四边形)定义的区域内仅将像素从A复制到B。 位图A和B具有相同的大小,并且四边形被定义为图像的像素空间中的四个{x,y}坐标。
最坏的情况是,我可以将每个像素的中心测试与四边形进行比较,以查看像素的中心是否在四边形内,但这非常慢。 有更好的算法吗?
我有两个位图,我想在一个由四个顶点(四边形)定义的区域内仅将像素从A复制到B。 位图A和B具有相同的大小,并且四边形被定义为图像的像素空间中的四个{x,y}坐标。
最坏的情况是,我可以将每个像素的中心测试与四边形进行比较,以查看像素的中心是否在四边形内,但这非常慢。 有更好的算法吗?
如果四边形是凸的,您可以使用以下算法:
简短版:对于每条扫描线(水平位图线),找到相交该扫描线的边缘,并复制它们之间的像素。
详细版:逐行进行扫描。从顶点(最小y)开始,并跟踪左右两侧的边缘。对于每个y值,计算两个边缘的x值(直接使用线性方程或使用 Bresenham算法)。然后将(xLeft,y)到(xRight,y)的像素复制到第二个位图中。
当到达边缘末端的顶点时,切换到与该顶点连接的另一个边缘。继续这样做,直到达到底部顶点。
对于凹四边形,这更加复杂。您可以使用类似的算法,但对于某些扫描线,将有四个边缘与扫描线相交。在这种情况下,您需要复制从边#1到#2和从边#3到#4之间的像素(按x值排序的边缘)。另一种选择是将四边形分成两个三角形,并在它们上面使用上述算法。