kev*_*n42 4 algorithm graphics bitmap computational-geometry
我有两个位图,我想只在像素位于由四个角(四边形)定义的区域内时才将像素从A复制到B. 位图A和B具有相同的大小,并且四边形被定义为图像的像素空间中的四个{x,y}坐标.
最糟糕的情况我可以测试每个像素的中心对着四边形,看看像素的中心是否在四边形内,但这非常慢.什么是更好的算法？
如果四边形是凸的,则可以使用此算法:
短版本:对于每条扫描线(水平位图线),找到与该扫描线相交的边,并复制它们之间的像素.
长版:按扫描线扫描扫描线.从顶部顶点开始(最小y),并跟踪左侧和右侧的边缘.对于每个y值,计算两条边的x值(直接使用线方程,或使用Bresenham算法).然后将(xLeft,y)处的像素复制到(xRight,y)到第二个位图.
当您到达边缘末端的顶点时,切换到连接到该顶点的另一边.继续这个直到到达底部顶点.
对于凹形四边形,这更复杂.您可以使用类似的算法,但对于某些扫描线,将有四条与扫描线相交的边.在这种情况下,您需要复制边#1到#2和#3到#4之间的像素(边缘按x值排序).另一种选择是将四边形分成两个三角形,并对它们使用上述算法.