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

Question

令P的光線是一個簡單的，但不一定是凸的，多邊形和q中的任意點在P.

設計一個有效的算法不一定找到一個線段自q始發相交P.

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

通過P的頂點子彈打中了信貸只有一面牆。

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

這是相同的，因爲這 this question但我無法理解的答案，更具體的答案似乎並不涉及Q，也是頭部和菸頭的事情並不清楚作爲一個多邊形的每個點會一個頭和一個屁股，因爲每個點都連接到兩個邊緣，如果這是有道理的。 謝謝

Answer 1

因此，任何不與頂點附近的多邊形相交的最佳答案都會有一個與多邊形的頂點幾乎相交的最佳答案。

也就是說，如果你有一個行經歷10「牆」，它是不是接近頂點，您可以在某些方向朝着頂點，同時仍保持10個牆壁相交的翻譯。

通過這種推理，你只需要搜索該通過近verticies解決方案。

所以verticies（nlogn）進行排序，然後搜索每個可能的線段，近一個相交（3N）。你可以做到這一點無需重新計算的全套交點對每個候選行，因爲該行從一個頂點移動到另一個，要麼添加或失去兩兩面牆（或保持不變）。您可以在每個步驟的恆定時間跟蹤這個增量變化。