掃線 - 它是什麼？

Question

有人可以試着向我解釋清掃線是什麼？我有數學和幾何基礎知識。請嘗試用我很可能會理解的語言來解釋。

此外，一個關於如何在某些程序（最好是Java）中實現的代碼示例會很好。

非常感謝

Answer 1

檢查@Josiah's link，但這個想法基本上是這樣的：

「掃」一條線空間（可能是2D），並採取了一些動作，當你遇到一個點，頂點，或其他物體。你可以用它來

• 附近建立一個點雲的邊界形狀

• 收縮包裝的積分獲得一個凸多邊形，

• 產生Voronoi圖（見上面的維基鏈接例子）

• 進行原始波模擬（掃描線或波陣面遇到的點會引起波形擾動）

• 可見性判定：在起始掃描線上選取觀察者位置（或甚至多個觀察者位置）。每次遇到物體時，從觀察者位置通過遇到物體的外邊界生成一個圓錐體或其他體積，表示遇到點後面的區域。

• 2D/3D排序，儘管這決不會是最有效的方式進行排序，

• 可能的事情，我都沒有想到的整體轉換。

更新

對於多邊形交集，你最好使用Separating Axis Test。 （針對Java示例的See this link）。

另外，see this link用於較少混淆的算法概述。