Choosing a subset from a larger 2d set?

Question

I have some objects with attributes x and y (position). I would like to receive and process those objects that are next to me (!), But ignore those that are out of range (*).

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

A slow approach would be to iterate over complete, unsorted, installed and ignore elements for which the distance is too great. However, I am going to have a large dataset and need fairly high performance.

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

Is there a good way to do this?

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

Answer 1

quadtree, .

R node Q .

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

, QuadTreeNode Rectangle bounds QuadTreeNode child[4].