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.

Answer 2

use a quadtree, and you have 3 types of qtree nodes:

1. node is outside of target rectangle: ignore
2. node is inside of target rectangle: include all points inside node
3. node is partially outside of rectangle: do a bounds check on points inside node

Answer 3

Please see this question. The Stony Brook Algorithm Repository has some implementations of KDTrees in C++, though they are not part of STL nor Boost.

Answer 4

Your sort function could check points as they are added for inside-the-rectangle-ness, and sort all points inside the rectangle before all points outside the rectangle. You would have to keep track of how many of each exist, or use a binary search on the entire set to find the cutoff point at lookup time.

Answer 5

Following Yuval F's link, I found Range Search, which appears to be the exact sort of thing you're looking for. I followed some links from there, and found CGAL, an open source C++ library, which implements a range search, with examples here.

Answer 6

Sorting an array takes O(nlog*n*) time. Simply checking each point individually (without sorting) takes O(n) time.

Ergo, just going through and checking each point is faster than sorting. And it's faster than building a quadtree too.

EDIT: If you have many rectangles to check, it's a different story. But if you only need to check a small, fixed number of rectangles then just do it the "obvious" way!