what datastructure / algorithm should I use for this?
I have a large number of points on a cartesian grid, locations specified by (x, y). I want to have a fast search, returning the set of points (objects) that lie within a given range of x and of y. (A rectangle within the grid).
Perhaps there's a lightweight framework that will do this?
Thanks
I would store the points as objects with two attributes: x and y, and a comparative function, which sorts them on one attribute or the other, using the remaining attribute as a tie breaker:
function Point(x, y){
this.x = x;
this.y = y;
this.compareTo =function(otherPoint){
if(otherPoint.x != this.x)
return this.x-otherPoint.x;
return this.y-otherPoint.y;
}
}
points[n] = new Point(someX, someY);
Then, you can use a sorting algorithm (such as QuickSort - with O(n log(n))) to sort them, and a simple insertion sort to keep them sorted as Points come and go. When you need to use your rectangle select, you can simply do a binary search across them (O(log(n))) to find the boundaries of the first attribute(say, x), then again across that smaller set to find the boundaries of the secont attribute(say, y), and the remaining set will be the ones you're looking for, making your search time (O(4 log(n)) worst case, and your your insert time linear(worst case). Not too shabby, if I do say so myself.
The following is the optimal implementation for the general problem:
