柵格化2D多邊形

Question

我需要從一個封閉的2D多邊形創建一個二進制位圖，表示爲點列表。你能否指點我一些有效率和足夠簡單的算法來做到這一點，或者更好一些C++代碼？

非常感謝！ PS：我想避免添加一個依賴項到我的項目中。但是，如果您建議使用開放源代碼庫，則始終可以查看代碼，因此它也可能很有用。

Answer 1

你想要的神奇的谷歌短語是「非零蜿蜒規則」或「甚至奇怪的多邊形填充」。

參見維基百科的條目：

• non-zero winding rule
• even odd polygon fill

兩者都非常容易實現，而且足夠快於大多數的目的。隨着一些聰明，他們也可以被製成antialiased。

Answer 2

• Triangulate your polygon
• 光柵的每個三角形的（如果你使用的是GPU，然後它可以爲你做到這一點，相反，它是GPU的原始操作）
  • 如果三角形沒有一個平行於x軸的線段，然後將其分成兩個三角形，線條平行於x軸並穿過它的中點y。現在剩下的任務是繪製一個三角形，該三角形具有一段平行於x軸的線段。這樣一個三角形有一個左側和一個右側的線段
  • 迭代三角形的掃描線（min-y到max-y）。對於每個y，計算該掃描線中的左側和右側線段的點。將掃描線段填入這兩點（一個簡單的memset）。

複雜度爲O（像素區）

Answer 3

可以在Pygame中檢查出的多邊形填充程序。看看draw_fillpoly函數。

該算法非常簡單。它找出每個段沿Y軸相交的所有位置。對這些交叉點進行排序，然後橫向填充每對交點。

這將處理複雜和相交的形狀，但顯然你可以粉碎這個算法與大量的段。

Answer 4

對於的"even-odd rule"

魯棒執行力度參見Darel Rex Finley's Efficient Polygon Fill，或它的Blender's version。

這是一種奇數/偶數填充方法，它支持自相交線，而不需要複雜的代碼來檢測這種情況，並且不依賴繞線（多邊形可以顛倒併產生相同的結果）。

---

更新，我做了DAREL雷克斯的方法的優化版本，避免遍歷所有座標對於每個y像素。

獨立實現：

• C99。
• Rust（帶測試）。

雖然增速將可能是指數，從快速測試，其周圍7.5倍更快（11X去除round呼叫時），利用繪製塗鴉在2540x1600的區域，情況因人而異任意手。