algorithm - applications - computational geometry中文




給定一組多邊形和一系列點,找出哪些多邊形是位於的點 (2)

如果點只能落在邊上,那麼只要檢查邊就可以找到O(n)中的多邊形。

否則,你必須對O(n log n)中的多邊形進行三角測試,以測試O(n)中的三角形。

您也可以通過從每個段延伸的線來劃分空間,注意哪一側在相應的多邊形的內部/外部。 如果一個點落在一個邊上,或者它位於多邊形的每個邊的內部,則這個點位於多邊形的內部。 在最壞的情況下,它的邊數是O(n),但在平均情況下趨向於O(m)的多邊形數。

一個R-tree在兩種情況下都會有所幫助,但前提是你有幾點要測試。 否則,構建R-tree將比查找三角形列表更加昂貴。

這是一個類似於這裡的問題 ,但我認為,如果我可以用更一般的術語來重新說明,這將是有幫助的。

我有一組多邊形,這些多邊形可以相互接觸,重疊,可以採取任何形狀。 我的問題是,給出一個點列表,如何設計一個有效的算法,找到哪些多邊形是位於點?

點的位置的一個有趣的限制是所有的點都位於多邊形的邊緣,如果這有幫助的話。

我知道r樹可以幫助 ,但是鑑於我正在做一系列的觀點,是否有一個更有效的算法,而不是逐個計算每個點?


我認為你對這個問題(這是一個準模擬感知)的直覺與對O(n)的必要計算方法的碰撞。

給定一個平面,一個退化的多邊形(一條線),以及任意一組點在平面上,這些點是否與該線相交或落在“上方”或“下方”? 即使對於這種退化的情況,我也想不出一種比O(n)小的方法。

不管怎樣,每個點都必須檢查它與線的關係,否則你不得不將點劃分成一些至少需要O(n)操作但很可能更多的樹狀結構。

如果我在計算幾何學方面做得更好,我或許可以有權威地說,你只是重申了克萊的測量問題,但是我只是要提出這個問題。





computational-geometry