二维空间中对象的高效数据结构
我有一个包含对象的二维空间，每个对象都有坐标向量和相对于其坐标的顶点数组，现在我需要一种有效的方式来存储对象，这个存储应该能够添加和删除对象，也是最重要的部分是碰撞检测：
我想获取有机会碰撞的对象列表（近邻等），应该快速而简单，大约
O([具有碰撞机会] * log([所有对象的数量])) 这样，当没有接近的对象时，它应该在 O(1) 中完成，而不是暴力方式只需在 O(n) 中遍历所有对象即可。
有什么不清楚的就问。
也许您知道有关该主题的一些链接或任何好主意。
谢谢。
I have a 2D space with objects, each object has coordinate vector and an array of vertexes relative to his coordinate, now I need an efficiency way of storing the objects, this store should be able to add and remove objects, also the most important part is the collision detection:
I want to get a list of objects which have a chance to collide (close neighbor etc.), should be fast and simple in about
O([number of objects with collision chance] * log([number of all objects])) so that way when there is no close objects it should do it in O(1) and not the brute force way of just going over all of the objects in O(n).
Ask if something not clear.
Maybe you know some link on the subject or any good ideas.
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
您可以使用 四叉树 来检查所有附近的对象。
you could use a quadtree for this to check all the nearby objects.
花栗鼠物理学和Box2D 都提供高效的 2D 碰撞检测。您可以使用其中之一，也可以仅检查其来源。
Chipmunk Physics and Box2D both offer efficient 2D collision detection. You could either use one of them, or just inspect their source.
您可以通过二进制空间分区来使用树数据结构，这里有一篇关于它的 wikipedia 文章。据我所知，这是在 n 维空间中存储有关对象位置信息的最有效方法。
它的工作原理如下： 假设您有以下字段
假设您有 100x100 的空间。
里面有 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 空间中查找对象。
You can use a tree data structure by using binary space partitioning, here is a wikipedia article about it. This is the most efficient way to my knowledge, of storing information about location of objects in an n-dimensional space.
Here is how it works: Let's say you've got the following field
Let's say you've got a space of 100x100.
You've got 6 objects in there with named A to F the co-ordinates
A(25,25)
B(25,75),
C(25,85),
D(75,75),
E(90,60)
Now, we divide our space into 4 parts, each part will be a childnode of the root node in the tree. The top left corner only contains point A, so that's a chield with one leafnode.
the bottom left corner contains 2 objects, B and C, so they'll be leaf nodes of the second chield.
Now the bottom right corner will have 3 elements in them, which we do not want because of the idea of a binary tree, so we make another subdivision. By doing that recursively, you get a very efficient data structure for finding objects in a 2D space.
您想要使用空间索引或四叉树。四叉树可以是简单的空间填充曲线 (sfc) 或希尔伯特曲线。 sfc 将 2d 复杂性降低为 1d 复杂性，并用于许多地图应用程序或热图。 sfc 也可用于存储邮政编码搜索。您想要搜索 Nick 的希尔伯特曲线四叉树空间索引博客。
You want to use a spatial index or a quadtree. A quadtree can be simple a space-filling-curve (sfc) or a hilbert curve. A sfc reduce the 2d complexity to a 1d complexity and is used in many maps applications or heat maps. A sfc can be used to store a zipcode search, too. You want to search for Nick's hilbert curve quadtree spatial index blog.