尋找點和物體碰撞的理想數據結構？

Question

我正在解決這個問題，我不知道要使用哪種數據結構。

我在2D平面上有多個對象（凸多邊形和圓形），對於給定的點，我必須計算點位於的對象（它們可以重疊）。

我一直在閱讀關於K-D樹木，但我不知道如何「彎曲」這種物體。我一直在閱讀關於邊界體積等級的內容，但我不知道它是否是最優的。

那麼，你認爲這個問題最好的數據結構是什麼？時間表現比內存使用更重要）。

謝謝！

Answer 1

大多數情況下，空間分割方案（如BVH，kd-tree，R-tree等）的「效率」來自智能樹構建。只要你可以很好地建立你的樹，你將會有快速的表現。對於你的情況，我會說kd-tree很好 - 它有很多可用的源代碼很常見。 R樹也是如此。我不明白你的意思是「彎曲」它爲你的對象。對於Kd-Tree，你必須決定的是一個軸對齊的平面 - 對於2D情況，如果圓（或多邊形）位於一邊或橫跨，它將是x = c或y = c。相當微不足道的問題。