我有一个2D空间的对象，每个对象都有坐标向量和一个相对于他的坐标的顶点数组，现在我需要一种有效的方式来存储对象，这个存储应该能够添加和删除对象，也是最重要的部分是碰撞检测：2D空间中对象的高效数据结构
我想获得一个对象的列表有机会碰撞（近邻等），应该是快速和简单的约
O([number of objects with collision chance] * log([number of all objects]))这样，当没有关闭对象时，它应该在O(1)中执行，而不是只使用g的蛮力方式覆盖了O(n)中的所有对象。
询问是否有不清楚的地方。
也许你知道一些关于这个主题或任何好主意的链接。
谢谢。
Chipmunk Physics和Box2D都提供有效的2D碰撞检测。你可以使用其中之一，或者只是检查它们的来源。
您可以通过使用二进制空间分区来使用树型数据结构，下面是关于它的wikipedia article。据我所知，这是存储有关n维空间中物体位置信息的最有效方式。
这里是如何工作的：假设你有以下字段
比方说，你已经有了100×100的空间。
你有6个对象中有一个名为A到F的坐标 A（25,25） B（25,75）， C（25,85）， d（75,75 ）， E（90,60）
现在，我们将空间分为4部分，每部分将成为树中根节点的一个子节点。左上角只包含A点，所以这是一个叶节点。 左下角包含2个对象B和C，因此它们将成为第二个屏幕的叶节点。 现在右下角会有3个元素，我们不希望因为二叉树的想法，所以我们再做一个细分。通过递归的方式，您可以获得一个非常高效的数据结构，用于在2D空间中查找对象。
您可以使用quadtree来检查所有附近的物体。
你想要使用空间索引或四叉树。四叉树可以是简单的空间填充曲线（sfc）或希尔伯特曲线。 sfc将2d复杂度降低到1d复杂度，并用于许多地图应用程序或热图。也可以使用sfc来存储邮政编码搜索。你想搜索Nick的希尔伯特曲线四叉树空间索引博客。