17

特定の長方形または円内のすべてのオブジェクトをすばやく取得できるように、それぞれが x 座標値と y 座標値を持つ一連のオブジェクトを格納する高速な方法を決定しようとしています。オブジェクトの小さなセット (~100) の場合、単にそれらをリストに格納し、それを反復処理する単純なアプローチは比較的迅速です。ただし、はるかに大きなグループの場合、これは遅くなると予想されます。次のコードを使用して、x座標でソートされたツリーマップとy座標でソートされたツリーマップのペアにもそれらを格納しようとしました。

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

これも機能し、より大きなオブジェクトのセットの方が高速ですが、それでも思ったより遅くなります。問題の一部は、これらのオブジェクトが移動し、このストレージに挿入し直す必要があることです。これは、ツリー/リストからオブジェクトを削除して再度追加することを意味します。そこにはもっと良い解決策があるはずだと思わずにはいられません。私はこれをJavaで実装していますが、違いがあれば、解決策はより有用なパターン/アルゴリズムの形になると思います。

4

6 に答える 6

14

四分木は、私が尋ねた特定の問題を解決するようです。 Kd ツリーは、2 次元だけでなく、任意の数の次元に対するより一般的な形式です。

R ツリーは、格納されているオブジェクトが単なる点ではなく、外接する四角形を持っている場合にも役立ちます。

これらのタイプの構造の一般的な用語は、空間インデックスです。

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

C＃での単純なQuadTreeの実装（Javaへの変換が簡単） http://www.codeproject.com/KB/recipes/QuadTree.aspx

于 2009-08-30T18:38:58.233 に答える
1

Kd-Treesをご覧ください。

于 2008-09-25T09:36:39.067 に答える
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 に答える