查找有多次相交的多邊形儘可能

這裏的光線是一個有趣的練習：查找有多次相交的多邊形儘可能

設P爲一個簡單的，但不一定是凸的，多邊形和q任意點不一定P.

設計一個高效的算法來找到一個線段從q個始發相交P.

的邊緣換言之的最大數量，如果站在點q，在什麼方向，你的目標應該是槍讓子彈會穿過最多的牆壁？

通過P的頂點的子彈只獲得一面牆的功勞。

O（n log n）算法是可能的。 n是頂點或邊的數量，因爲它是一個多邊形，邊的數量大致等於頂點的數量。

這裏是我的想法：

連接Q隨所有的頂點（假設有N個頂點）的P個第一。將會有N條線或N-1條線。

最後的射門線必須位於這兩對之間。所以我們必須找到包含最多邊數的對。

我不認爲這個解決方案是O（n log n）。

任何想法？

來源

2012-05-06 Jackson Tale

哇，我不知道。出於好奇，這裏是什麼？邊緣的數量？ – Jeremy

我相信這個問題是相關的：http://stackoverflow.com/questions/4446112/search-for-interval-overlap-in-list-of-intervals你可以表示P中的每個線段作爲一對弧度值來自q的射線必須落在其間。 –

圖像應該沒問題。 –

嗯，首先改造點的座標成P.

中心不失一般性極性系統，我們選擇順時針方向相對於角座標特殊。
現在讓我們進行沿多邊形的所有邊依次圓形的步行路程，讓我們看到的起點和那些邊緣，那裏的步行帶我們沿順時針方向相對於P.
讓我們的終點將這種邊緣的終點稱爲'屁股'，起點爲'頭部'。這一切都應該在O（n）中完成。現在我們必須對這些頭部和尾部進行排序，所以快速排序可能是O(nlog(n))。我們按照它們從最小φ向上的角度（φ）對它們進行排序，確保在φ座標相等的情況下，頭部被認爲小於尾部（這對於符合問題的最後一個規則是重要的）。
一旦完成，我們將從最小的φ開始步行，每遇到一個屁股就增加運行總和，並且每當遇到一個頭時遞減，注意到一個全局最大值，這將是φ座標上的一個區間。這也應該在O（n）中完成，因此總體複雜度爲O(nlog(n))。

現在你會告訴我你爲什麼問這樣的問題？

來源

2012-05-06 21:32:14

謝謝你回答這個問題。你可以編輯你的答案看起來更好嗎？ –

這是算法設計手冊中的一個重要內容。 –

有人可以解釋一點點細節，尤其是第三點和第四點@BorisStitnicky – KingJames

我使用了Boris Stitnicky的算法，並在Java中編寫了我的解決方案。但是我選擇了逆時針方向，並檢查一個區間的哪個點是起始點，以及我使用叉積的區間的結束點。你可以在這裏找到它：https://github.com/Katkov/algorithms/blob/master/BulletAgainstWalls.java

來源

2015-01-26 05:51:29

查找有多次相交的多邊形儘可能

回答

相關問題