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]
.