Fast algorithm to find all points inside a rectangle

Question

Given a set of distinct points in 2D space, and a rectangle (coordinates of all four points, sides parallel with xy axis) how can I quickly find which points are inside the rectangle?

I'm not interested in the basic solution of going through all points and seeing which one is inside the rectangle. What I'm looking for is an algorithm which will give me fast query times per rectangle.

I don't care how much time I spend in the preprocessing step. What I do care is that after I process my data I obtain a useful structure which gives me fast query times per rectangle.

I know for example I can count how many points I have inside a rectangle in O(logN). That works because I do a lot of heavy processing in the beginning and then query the processed data with a new rectangle every time and get a new count in logN time. I'm looking for a similar algorithm for finding the actual points not just their count.

Answer 1

A classical answer is the kD-tree (2D-tree in this case).

For a simple alternative, if your points are spread uniformly enough, you can try by gridding.

Choose a cell size for a square grid (if the problem is anisotropic, use a rectangular grid). Assign every point to the grid cell that contains it, stored in a linked list. When you perform a query, find all cells that are overlapped by the rectangle and scan them to traverse their lists. For the partially covered cells, you will need to perform the point-in-rectangle test.

The choice of the size is important: too large can result in too many points needing to be tested anyway; too small can result in too many empty cells.

Answer 2

You are looking for kd-tree range search or range query.

• Quadtrees (or octtrees or 16-trees...) are better when there is a changing set of points, but you expect the distribution to be uniform. No further balancing steps are needed, because the structure of the tree is fixed.
• kd-trees perform better on a fixed set of point, even with non-uniform distribution. When the point set changes, it is hard (but not impossible) to do self-balancing steps.
• AABB trees (or fat AABB trees) provide a fast way for testing overlapping shapes, not only points. AABB trees need some balancing occasionally. When constantly moving objects are included, common way is to use "fat AABB-s", so you don't have to update the tree in every frame.
• Sorting by only one axis and using binary search (something like abelenky suggested, but I think there is no point in doing a second binary search) is a simple and elegant solution, but will be slow when for example you sort by the X axis, and all the points are on a line parallel with Y. You have to do a linear filtering on the points which are matched by the binary searches by X. Time complexity is worst case O(n), but this worst case happens pretty often.

All these algorithms run queries in average O(log n + k) where k is the count of matched points.

Gridding, like Yves suggested, can perform range search in O(k) time, but only when the size of the query rectangle is bounded. This is what they often do in particle simulations. Gridding can be used even when the input set is not bounded -- just make a fixed count of buckets based on hash of the grid coordinates. But if the query rectangle can be of arbitrary size, then gridding is a no-go.

Answer 3

You could group point in sectors. If a sector is completely in or out of given rectangle then all point within it are also in or out. If a sector is partially in then you have to search O(n) for points in that sector to check if they are in the rectangle. Look for k-d tree search.

Answer 4

Along with other answers, you can also look into Morton codes (z-order curve sorting).

In your case, that is static data, you can even represent the whole point data as an array.

https://en.wikipedia.org/wiki/Z-order_curve

This paper also have a rather complicated timeline of different "multi-dimentional access methods" --http://www.cc.gatech.edu/computing/Database/readinggroup/articles/p170-gaede.pdf