Picking a subset out of a greater 2d set?

Question

I'm having some objects with attributes x and y (positions). I would like to obtain and process those of the objects that are nearby me (!) but ignore the ones that are out of range (*).

 __________________________
|   __________             |
|  |     !    | *          |
|* |         !|      *     |  -me = center of subset
|  |    me    |            |  -!  = elements of subset
|  |  !       |            |  -*  = elements of full set, not visible
|  |_______!__|   *       *|
|__________________________|

The slow approach would be to iterate the complete ,unsorted, set, and ignore elements those for which the distance is too big. However i'm going to have a big dataset, and need quite some performance.

Instead I'm looking for a way to select only the nearby elements to start with. Maybe by sorting the 2d set in some way, and only iterate the set over a certain range (from the subset's border to border).

Is there a good way to do this?

(note: the objects' positions are static, and the set can be pre-processed)

Answer 1

Construct a quadtree containing all your points.

Given query rectangle R and quad tree root node Q, the pseudocode for the query algorithm is as follows.

query(Rectangle R, QuadTreeNode Q)
    if R and Q.bounds are disjoint
        yield no points
    else if R contains Q.bounds
        yield all points in the subtree of Q
    else (if R intersects Q.bounds)
        yield all points in query(R, Q.child[i]) for i = 0, 1, 2, 3

This assumes a QuadTreeNode has Rectangle bounds and QuadTreeNode child[4].