Storing objects for locating by x,y coordinates

Question

I'm trying to determine a fast way of storing a set of objects, each of which have an x and y coordinate value, such that I can quickly retrieve all objects within a certain rectangle or circle. For small sets of objects (~100) the naive approach of simply storing them in a list, and iterating through it, is relatively quick. However, for much larger groups, that is expectedly slow. I've tried storing them in a pair of TreeMaps as well, one sorted on the x coordinate, and one sorted on the y coordinate, using this code:

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

This also works, and is faster for larger sets of objects, but is still slower than I would like. Part of the problem is also that these objects move around, and need to be inserted back into this storage, which means removing them from and re-adding them to the trees/lists. I can't help but think there must be better solutions out there. I'm implementing this in Java, if it makes any difference, though I expect any solution will be more in the form of a useful pattern/algorithm.

Answer 1

A quadtree is the structure which is usually used for that.

Answer 2

Have a look at Kd-Trees.

Answer 3

The general term is a Spatial Index. I guess you should choose according to the existing implementations.

Answer 4

Quadtrees seem to solve the specific problem I asked. Kd-Trees are a more general form, for any number of dimensions, rather than just two.

R-Trees may also be useful if the objects being stored have a bounding rectangle, rather than being just a simple point.

The general term for these type of structures is Spatial Index.

There is a Java implementation of Quadtree and R-Tree.

Answer 5

You could put all the x cords in a map, and the y cords in another map, and have the map values point to the object.

  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

Simple QuadTree implementation in C# (easy to translate into java) http://www.codeproject.com/KB/recipes/QuadTree.aspx