找到所有由線交點形成的多邊形

Question

我有一個由線段描述的迷宮（沒有給定順序）。給定一點，我需要確定它是否在迷宮裏面或者沒有。一切都在卡特契亞飛機上（沒有離散化）。

---

我的想法是如下改造問題：

鑑於飛機的一些線段與頂點給定段的終點，並與兩側躺在段，找到所有多邊形（你可以在下面的圖片中看到，你不能假設雙方會形成一個分段子集）。

然後只是檢查：如果一個點只在一個多邊形裏面，那麼它在迷宮裏面，否則沒有。

---

我想到的解決方案是：散列端點和線相交，然後查找循環。

其他建議？ 謝謝！

（忽略圖像中的顏色）

Answer 1

這足以找到邊界（外）多邊形。這可以通過在邊界上找到一個點並且從該點沿着一個方向逐段地遍歷來完成。如果有更多的可能性比選擇'外部'更有可能。可謂算法：

find boundary point 
find first direction to go and go to that point 
while current point is different than fist one 
    find next direction to go 
    go to next point 

第一點可以發現，與最高的Y座標點，如果有更多這樣的比不帶當中最低的X。我們可以稱之爲左上角點。

要走的第一個方向：第一個點連接到其他點，並且這些點具有< = Y座標，這意味着連接線段在第一個點以下。選擇最右邊的。

下一個要走的方向：當前點由某個（進入）段達到，下一個段要從進入段進入正向最遠，與從進入段到順時針方向第一個段相同。