Lưu trữ các đối tượng để định vị theo toạ độ x, y

Question

Tôi đang cố gắng xác định một cách nhanh chóng để lưu trữ một bộ đối tượng, mỗi đối tượng có giá trị tọa độ x và y, sao cho tôi có thể nhanh chóng truy xuất tất cả các đối tượng trong một hình chữ nhật hoặc hình tròn. Đối với các bộ đối tượng nhỏ (~ 100) cách tiếp cận ngây thơ của việc lưu trữ chúng đơn giản trong một danh sách, và lặp lại thông qua nó, tương đối nhanh. Tuy nhiên, đối với các nhóm lớn hơn nhiều, đó là dự kiến ​​chậm. Tôi đã thử lưu trữ chúng trong một cặp Bản đồ cây là tốt, một sắp xếp trên tọa độ x, và một sắp xếp trên tọa độ y, sử dụng mã này:

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

này cũng làm việc, và là nhanh hơn cho lớn hơn bộ đối tượng, nhưng vẫn chậm hơn tôi muốn. Một phần của vấn đề cũng là các đối tượng này di chuyển xung quanh, và cần phải được đưa trở lại vào bộ nhớ này, có nghĩa là loại bỏ chúng khỏi và thêm chúng vào cây/danh sách. Tôi không thể không nghĩ rằng phải có giải pháp tốt hơn trên mạng. Tôi đang thực hiện điều này trong Java, nếu nó làm cho bất kỳ sự khác biệt, mặc dù tôi hy vọng bất kỳ giải pháp sẽ được nhiều hơn trong các hình thức của một mô hình/thuật toán hữu ích.

Answer 1

A quadtree là structure thường được sử dụng cho điều đó.

Answer 2

Hãy xem Kd-Trees.

Answer 3

Thuật ngữ chung là Spatial Index. Tôi đoán bạn nên chọn theo existing implementations.

Answer 4

Quadtrees dường như giải quyết được vấn đề cụ thể mà tôi đã hỏi. Kd-Trees là một dạng tổng quát hơn, cho bất kỳ số thứ nguyên nào, thay vì chỉ hai.

R-Trees cũng có thể hữu ích nếu các đối tượng được lưu trữ có hình chữ nhật bị ràng buộc, thay vì chỉ là một điểm đơn giản.

Thuật ngữ chung cho các loại cấu trúc này là Spatial Index.

Có triển khai Java Quadtree và R-Tree.

Answer 5

Bạn có thể đặt tất cả các x dây vào bản đồ và các dây y trong bản đồ khác và có giá trị bản đồ trỏ đến đối tượng.

 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

đơn giản thực hiện quadtree trong C# (dễ dàng để dịch sang java) http://www.codeproject.com/KB/recipes/QuadTree.aspx