我有一个2D空间的对象,每个对象都有坐标向量和一个相对于他的坐标的顶点数组,现在我需要一种有效的方式来存储对象,这个存储应该能够添加和删除对象,也是最重要的部分是碰撞检测:2D空间中对象的高效数据结构
我想获得一个对象的列表有机会碰撞(近邻等),应该是快速和简单的约
O([number of objects with collision chance] * log([number of all objects]))
这样,当没有关闭对象时,它应该在O(1)
中执行,而不是只使用g的蛮力方式覆盖了O(n)
中的所有对象。
询问是否有不清楚的地方。
也许你知道一些关于这个主题或任何好主意的链接。
谢谢。