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.

Electoral

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.

Align

Answer 2

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.

Anemograph

Answer 3

Sorting an array takes O(nlogn) 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!

Tumble

If you build a quadtree, you only do it once. Then your search is only O(log n), which is faster. – Though

What's your point? I already addressed this in my answer. If you only need to check 1 rectangle, constructing a quadtree is a much slower method. – Tumble

If the rectangles move around, keeping the quadtree up-to-date will eat up a lot of time as well. – Broomfield

Answer 4

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

Sugared

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.

Jimmy

Answer 6

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.

Hearts