17

我正在尝试确定一种存储一组对象的快速方法，每个对象都有一个 x 和 y 坐标值，以便我可以快速检索某个矩形或圆形内的所有对象。对于小型对象集（约 100 个），简单地将它们存储在列表中并遍历它的简单方法相对较快。然而，对于更大的群体来说，这预计会很慢。我也尝试将它们存储在一对 TreeMaps 中，一个按 x 坐标排序，一个按 y 坐标排序，使用以下代码：

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

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

4

6 回答 6

14

四叉树似乎解决了我问的具体问题。 Kd-Trees是一种更通用的形式，适用于任意数量的维度，而不仅仅是两个维度。

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

这些类型结构的通用术语是空间索引。

Quadtree和R-Tree有一个 Java 实现。

于 2008-09-25T10:37:32.807 回答
4

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

于 2008-09-25T09:51:29.203 回答
2

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

于 2008-09-25T09:34:00.617 回答
1

看看Kd 树。

于 2008-09-25T09:36:39.067 回答
1

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

于 2009-08-30T18:38:58.233 回答
0

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

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