Using an STL map to find points in a rectangular area?

Question

I have many x, y points with me, and each x, y point has some additional data associated with it. I will store these additional data in the structure. My application requires that, given any one point, I need to find how many other points lie inside the rectangular area surrounding this point (this point is in the center of the rectangle).

One logic that I was thinking about is to store all the points x as keys on map A, and all y points to the keys on another map B. Map A will have the value x as the key value and y as the value . Map B will have y as the key and related structure as the value.

Thus, if the given point is (10.5, 20.6), I can use upper_bound (10.5 + RECTANGLE_WIDTH) and lower_bound (10.5-RECTANGLE_WIDTH) to find the range of x values ​​that lie inside the rectangle, and for the corresponding y values, find if the values ​​are y within the + - range of 20.6.

The whole point of using the map was that I have a massive array of x, y points, and the search should be performed every two seconds. So I had to use log (n) map search. I feel this can be done in a more efficient way. Suggestions?

Answer 1

This is a typical quadtree app. The square makes it easy to find the points m lying in your rectangle in O (log (n) + m), where n is the total number of points.

Edit: your map approach is not so effective. For randomly distributed points, it will have an average complexity of O (sqrt (n)) and O (n) in the worst case.

Answer 2

How about the fact that you store points as a simple 2-dimensional array of pointers to these structures, and when you need to find the point x, y is a simple index operation. The same applies to any other points (x + a, y + b).

Answer 3

If you use std :: map of points, the search will always be O (log N), where N is the number of points you have.

Another option is to divide the search space into buckets and place your point in the buckets. Then you calculate in your rectangle:

• any buckets for which all points are inside your rectangle
• anyone for which there is some overlap.

For those who have some overlap, you can search in your collection, which is O (M), if you use the correct type of collection for each bucket, but M should be less than N. It may even be that M rarely exceeds a handful in in this case, you can probably check them out linearly.

Developing which braids overlap is a constant operation of the time, but you have to go through these linearly (even to check if they are empty), so too many of them can also be a problem.

Answer 4

The first observation would be that std::map would not be the most efficient structure anyway. Your input is pretty much corrected, apparently (from the comments). In this case, std::binary_search on a sorted std::vector is more efficient. The main advantage of std::map over std::vector is that the insert is O (log N) instead of O (N), and you don't need it.

The next observation would be that you can allow yourself a little inaccurate in the first step. Your output set is likely to be much smaller than the total number of points (otherwise a linear search will be fine). But assuming this is so, you can take advantage of rounding the rectangle. This will result in more candidate points, which you then check against the exact border.

For example, if your points were randomly distributed in the XY plane between (0,0) and (200,300), you could create a 20x30 matrix, each of which had a 10.10 subarea. If now you need points in the rectangle from (64,23) to (78, 45), you need to check the subareas [6,2], [6,3], [6,4], [7,2], [7,3] and [7,4] - only 6 out of 600. In the second stage, you throw out results such as (61, 25).