寻找点和物体碰撞的理想数据结构？

Question

我正在解决这个问题，我不知道要使用哪种数据结构。

我在2D平面上有多个对象（凸多边形和圆形），对于给定的点，我必须计算点位于的对象（它们可以重叠）。

我一直在阅读关于K-D树木，但我不知道如何“弯曲”这种物体。我一直在阅读关于边界体积等级的内容，但我不知道它是否是最优的。

那么，你认为这个问题最好的数据结构是什么？时间表现比内存使用更重要）。

谢谢！

Answer 1

大多数情况下，空间分割方案（如BVH，kd-tree，R-tree等）的“效率”来自智能树构建。只要你可以很好地建立你的树，你将会有快速的表现。对于你的情况，我会说kd-tree很好 - 它有很多可用的源代码很常见。 R树也是如此。我不明白你的意思是“弯曲”它为你的对象。对于Kd-Tree，你必须决定的是一个轴对齐的平面 - 对于2D情况，如果圆（或多边形）位于一边或横跨，它将是x = c或y = c。相当微不足道的问题。