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.