如何查找多邊形內的線段列表

Question

我有一條線和一個多邊形。該線可以部分在內部並且部分在多邊形之外。該線可以在單點或多點處與多邊形相交。線條的實施例被示出爲下面

請參考圖片。對於水平的紅色線，我想獲得線段列表。期望的輸出是（A-B）（C-D）（E-F），對於垂直線我想要得到線段1-2。

我經歷了how to detemine if a line segment is inside of a polygon?等堆棧溢出問題。

但無法獲得最優化的算法以獲取多邊形內的線段列表。

我也通過以下鏈接 https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm但我的問題是有更多的優化算法來查找多邊形內的線段？

Answer 1

我回答的情況是，不允許進行預處理，即您有一條線段（或幾條）來處理給定的多邊形。多邊形是一般的（並且可以帶有孔）。

旋轉線條使其水平，同時旋轉多邊形頂點。

然後，如果端點具有不同符號的縱座標，那麼多邊形的一側會與段的支撐線相交。在這種情況下，您可以計算交叉點的位置。

多邊形內部的子段由在段端點之間找到的有序交點組成。