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

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

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

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

Answer 1

Quadtrees似乎解决了我问的具体问题。 Kd-Trees是一种更通用的forms，适用于任何数量的维度，而不仅仅是两个维度。

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

这些类型结构的总称是空间索引 。

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

Answer 2

一般术语是空间索引 。 我想你应该根据现有的实现来选择。

Answer 3

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

Answer 4

看看Kd-Trees 。

Answer 5

C＃中简单的QuadTree实现（易于翻译成java） http://www.codeproject.com/KB/recipes/QuadTree.aspx

Answer 6

您可以将所有x条线放在地图中，将y绳索放在另一个地图中，并使地图值指向该对象。

  TreeMap> xMap = new TreeMap>(); for (int x = 1; x < 100; x += 2) for (int y = 0; y < 100; y += 2) { Point p = new Point(x, y); TreeMap tempx = xMap.get(x); if (tempx == null) { tempx = new TreeMap(); xMap.put(x, tempx); } tempx.put(y, p); } SortedMap> tempq = xMap.subMap(5, 8); Collection result = new HashSet(); for (TreeMap smaller : tempq.values()) { SortedMap smallerYet = smaller.subMap(6, 12); result.addAll(smallerYet.values()); } for (Point q : result) { System.out.println(q); } }