什麼是有效的算法來複制四邊形內的像素？

Question

我有兩個位圖，並且我想只在像素位於由四個角（四邊形）定義的區域內時纔將像素從A複製到B.位圖A和B的大小相同，並且四邊形在圖像的像素空間中定義爲四個{x，y}座標。

最糟糕的情況我可以測試每個像素的四邊形的中心，看看像素的中心是否在四邊形內，但是這非常慢。什麼是更好的算法？

Answer 1

如果四邊形是凸的，你可以用這個算法：

短版：對於每個掃描線（水平位線），發現該交叉掃描線的邊緣，並複製它們之間的像素。

長版：按掃描線進行掃描。從頂部頂點（最小y）開始，並跟蹤左側和右側的邊緣。對於每個y值，計算兩條邊的x值（直接使用直線方程或使用Bresenham's algorithm）。然後將（xLeft，y）處的像素複製到（xRight，y）到第二個位圖。

當您到達邊緣末端的頂點時，切換到連接到該頂點的另一邊。繼續這個直到到達底部頂點。

對於凹四邊形，這是比較複雜的。您可以使用類似的算法，但對於某些掃描線，會有四條邊與掃描線相交。在這種情況下，您需要複製邊緣＃1到＃2和＃3到＃4之間的像素（邊緣按x值排序）。另一種選擇是將四邊形分成兩個三角形，並在其上使用上述算法。