logo标签列表

存储物品以便通过x，y坐标进行定位

javatreespatialquadtree
17

我正在尝试确定一种快速存储一组对象的方法，每个对象都有x和y坐标值，以便我可以快速检索某个矩形或圆周内的所有对象。 对于小的对象集（~100），简单地将它们存储在列表中并进行迭代是相对快速的。但是，对于更大的组，这样做会变得非常缓慢。 我还尝试将它们存储在一对TreeMaps中，一个按x坐标排序，另一个按y坐标排序，使用以下代码：

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

这种方法也有效，对于更大的对象集合速度更快，但仍比我想要的慢。 问题的部分原因是这些对象会移动，需要重新插入到这个存储中，这意味着将它们从树/列表中删除并重新添加。 我不禁想到一定有更好的解决方案。 如果有什么区别的话，我是在Java中实现这个，尽管我期望任何解决方案都更像是一个有用的模式/算法。

6个回答
14

四叉树似乎可以解决我提出的特定问题。Kd-Tree是一种更通用的形式，适用于任意维数，而非仅限于二维。

R-Tree如果被存储的对象具有边界矩形而不仅仅是简单的点，则也可能会有用。

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

Java实现了四叉树和R-Tree。

4
2
1
1
0
你可以将所有的x坐标放在一个map中，将y坐标放在另一个map中，并让map值指向对象。
        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);
            }
    }
如果你处理的是连续平面上的点而不是几个离散点，你可以通过使用特定大小的“桶”来改善这个问题。虽然不如四叉树好，但实现起来更简单。 - Paul Tomblin
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接