algorithm - 二维空间对象的高效数据结构

Question

我有一个包含对象的二维空间，每个对象都有坐标向量和一个相对于他的坐标的顶点数组，现在我需要一种存储对象的有效方法，这个存储应该能够添加和删除对象，还有最重要的部分是碰撞检测:

我想得到一个有机会碰撞的对象列表(近邻等)，应该快速简单地在大约

O([具有碰撞机会的对象数量] * log([所有对象的数量])) 这样当没有接近的对象时它应该在 O( 1) 而不是仅遍历 O(n) 中的所有对象的蛮力方式。

有什么不明白的就问。

也许您知道有关该主题的一些链接或任何好的想法。

谢谢。

Answer 1

你可以使用 quadtree为此检查附近的所有物体。