代码之家 › 专栏 › 技术社区 › Timothy Pratley

我应该如何索引一个简单的矩形世界?

geometry data-structures algorithm

1

Timothy Pratley · 技术社区 · 16 年前

这个世界由许多大小相似的(1K-10K)矩形组成,我需要能够在尝试添加新矩形时快速确定潜在的重叠。将动态添加和删除矩形。R-树在这里合适吗?如果是这样,有没有好的图书馆我应该考虑?(我愿意接受任何语言的建议)。

2 回复 | 直到 16 年前

1

3

Rik Heywood 16 年前

是的,R-树是合适的。

quad trees 也是一个很好的数据结构,可以快速地在二维空间中找到物体。它们实际上是R-树的一个更统一的版本。使用这些结构,您可以在一个很小的空间区域内快速归零,只需很少的测试,即使是使用大量的数据集。

有一个C实现 here 尽管我没看过。

这种数据结构(它的3D版本称为 Octrees )通常在游戏中用来管理大型数据集的对象,这些对象需要知道它们是否靠近任何其他对象进行碰撞测试,以及各种其他有趣的原因。

你应该能够在游戏产业网站上找到很多关于这些数据结构的文章和例子,比如 gamasutra 和 opengl.org

2

1

Matthieu M. 16 年前

你也可以仰视 kd-trees .

我不知道有什么实现,但至少在3D中,它们通常被认为比八叉树更具性能。例如,这里是经验的回归 I just googled it .

如果遇到性能问题,您可能需要考虑使用四叉树的替代方法。

但值得注意的是,杜鹃树很难再平衡…