复制四边形内像素的有效算法是什么？
我有两个位图，并且仅当像素位于由四个角（四边形）定义的区域内时，我才想将像素从 A 复制到 B。位图 A 和 B 大小相同，四边形定义为图像像素空间中的四个 {x,y} 坐标。
最坏的情况是，我可以针对四边形测试每个像素的中心，看看像素的中心是否在四边形内部，但这非常慢。什么是更好的算法？
I have two bitmaps, and I want to copy pixels from A to B only when the pixels are inside an area defined by four corners (a quadrangle). Bitmap A and B are the same size and the quadrangle is defined as four {x,y} coordinates in the pixel space of the image.
Worst case scenario I can test the center of each pixel against the quad to see if the pixel's center is inside the quad, but this is very slow. What is a better algorithm?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果四边形是凸的，则可以使用以下算法：
简短版本：对于每条扫描线（水平位图线），找到与该扫描线相交的边缘，并复制它们之间的像素。
长版：逐条扫描线。从顶部顶点（最小 y）开始，并跟踪左侧和右侧的边缘。对于每个 y 值，计算两条边的 x 值（直接使用直线方程，或使用 布雷森纳姆算法）。然后将 (xLeft,y) 到 (xRight,y) 处的像素复制到第二个位图。
当到达边末端的顶点时，切换到连接到该顶点的另一条边。继续此操作直到到达底部顶点。
对于凹四边形，情况更为复杂。您可以使用类似的算法，但对于某些扫描线，将有四个边缘与扫描线相交。在这种情况下，您需要复制边缘 #1 到 #2、#3 到 #4 之间的像素（边缘按 x 值排序）。另一种选择是将四边形分成两个三角形，并对它们使用上述算法。
If the quadrilateral is convex, you can use this algorithm:
Short version: For each scanline (horizontal bitmap line), find the edges that intersect that scanline, and copy the pixels between them.
Long version: Go scanline by scanline. Start at the top vertex (minimum y), and keep track of the edges at the left and right sides. For each y value, calculate the x value of the two edges (either using the line equation directly, or using Bresenham's algorithm). Then copy the pixels at (xLeft,y) to (xRight,y) to the second bitmap.
When you reach a vertex at the end of a edge, switch to the other edge connected to that vertex. Continue this until reaching the bottom vertex.
For concave quads, this is more complicated. You can use a similar algorithm, but for some scanlines there will be four edges intersecting the scanline. In that case, you need to copy the pixels between edge #1 to #2, and #3 to #4 (with the edges ordered by x value). Another option is to separate the quad into two triangles, and use the above algorithm on them.