存儲對象用於定位x，y座標

Question

我試圖確定一種快速存儲一組對象的方法，每個對象都有一個x和y座標值，這樣我就可以快速檢索某個對象中的所有對象矩形或圓形。 對於小組對象（〜100）來說，簡單地將它們存儲在一個列表中並迭代它的方法相對較快。但是，對於更大的羣體而言，預計會很慢。 我試過一對樹狀的存儲它們，以及，一個在x座標進行排序，並在y一個排序的座標，使用此代碼：

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

這也適用，並且是更大更快對象組，但仍然比我想要的慢。 部分問題還在於這些對象四處移動，需要插回到此存儲中，這意味着將它們從樹中刪除並重新添加到樹/列表中。 我不禁想到那裏一定有更好的解決方案。 我在Java中實現它，如果它有所作爲，但我期望任何解決方案將以更有用的模式/算法的形式出現。

Answer 1

A quadtree是structure它通常用於此。

Answer 2

看看Kd-Trees。

Answer 3

通用術語是Spatial Index。我想你應該選擇根據existing implementations。

Answer 4

Quadtrees似乎解決了我問的具體問題。 Kd-Trees是一個更一般的形式，適用於任何數量的維度，而不僅僅是兩個維度。如果正在存儲的對象具有一個矩形邊框，而不是隻是一個簡單的點

R-Trees也可能是有用的。

這些類型結構的通用術語是Spatial Index。有一個Quadtree和R-Tree的Java實現。

Answer 5

你可以把貼圖中所有的x線，而Y線的另一個地圖，並有地圖值指向的對象。在C＃

 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); 
      } 
    } 

Answer 6

簡單的四叉樹實現（容易轉化成Java） http://www.codeproject.com/KB/recipes/QuadTree.aspx