Store 2D points for quick retrieval of those inside a rectangle

Question

I have a large number of 2D points and I want to quickly get those that lie in a certain rectangle. Let's say a '.' is any point and 'X' is a point I want to find inside a rectangle which has 'T' as TopLeft and 'B' as BottomRight points:

. . . . . .
. T-----+ .
. | X X | .
. +-----B .
. . . . . .

I have tried a std::set with a sort functor which sorts the TopLeft point at the beginning and the BottomRight at the end of the set. When sorting by X value first, this would result in the following points being found.

. . . . . .
. T-----+ .
X | X X | X
. +-----B .
. . . . . .

This means I would have to check each found point, whether it really is inside the rectangle. Not really good.

What would be a better way to do this?

My language is C++ (Windows) and I have the STL as well as boost available.

Update

Having read the answers so far, I noticed that I haven't accounted for all parameters of my problem: There is not one fixed rectangle. Rectangles can be set by the user at runtime. This means sorting the set of points promises to be more efficient than a linear search through all points as suggested by Artelius before this update. I will still give it a try, though! I don't expect the user to set a rectangle very frequent. So regarding the implementation effort it might show up to be a good solution for me.

Answer 1

You could store the points in a spatial index using quad or r-trees. Then given the rectangle you could find all the nodes of the tree that overlap it, you would then have to compare each point in this subset to see if it falls in the rectangle.

In essence, the spatial tree helps you prune the search space.

You might be able to use a simpler solution, such as partitioning the points in ranges. Say where x is from 0,10 as one range, 11,20 as another. Any solution that lets you prune the search space will help.