存储用于通过x,y坐标定位的对象

Question

我正在尝试确定一种存储一组对象的快速方法,每个对象都有一个x和y坐标值,这样我就可以快速检索某个矩形或圆形内的所有对象.对于小型对象集(~100),简单地将它们存储在列表中并通过它迭代的简单方法相对较快.然而,对于更大的群体来说,预计会很慢.我已经尝试将它们存储在一对TreeMaps中,一个在x坐标上排序,一个在y坐标上排序,使用以下代码:

xSubset = objectsByX.subSet( minX, maxX );
ySubset = objectsByY.subSet( minY, maxY );
result.addAll( xSubset );
result.retainAll( ySubset );

这也有效,并且对于较大的对象集更快,但仍然比我想要的慢.部分问题还在于这些对象四处移动,需要插回到此存储中,这意味着将它们从树中删除并重新添加到树/列表中.我不禁想到那里必须有更好的解决方案.我在Java中实现这个,如果它有任何区别,虽然我希望任何解决方案都会以有用的模式/算法的形式出现.

Answer 1

Quadtrees似乎解决了我问的具体问题. 对于任何数量的维度,Kd-Trees都是更通用的形式,而不仅仅是两个维度.

如果存储的对象具有边界矩形,而不仅仅是一个简单的点,则R树也可能很有用.

这些类型结构的一般术语是空间索引.

有一个Quachiree和R-Tree的Java实现.

Answer 2

四叉树是通常用于此目的的结构。