Suppose I have a 2D grid of intervals. A set of intervals along the x-axis and the same along the y-axis. Now I have to determine which intervals in x-axis and y-axis a new object belongs two. Let's say a new object has to numbers, one a x-coordinate and the other a y-coordinate. By determining the interval in x and y which the object fits into, I would like to retrieve some stored data.
I thought of something like a std::map<IntervalX, IntervalY, DataToStore> map or std::multimap<IntervalX, IntervalY, DataToStore> map. Any suggestions on how implement this, so that retrieving the stored data for the interval pair is quite efficient/fast and not in O(n²).
EDIT: An interval is determined by two float values. For example: An interval along the x-axis [0.5, 3.0). So 0.5 is contained and 3.0 would be not included in this interval but in the next interval in the positive x-direction.
The intervals are disjoint and not overlapping nor nested. The union of the intervals is some complete segment of the line. I did tile the plane in a set of rectangles and I want to know which rectangular region the point falls in.
For example: Intervals along x-axis staring at 0 to 10 with an interval size of 0.5 and along the y-axis starting at 2 to 15 with an interval size of 1.0. A given Point P(x=0.7,y=3.0) in which interval does it fall? It's the interval 2 on the x-axis and interval 2 on the y-axis. Now I need to retrieve the data stored for that interval pair.
In my use case, I will have around 10000 intervals along each axis and the determination of an interval for an object has to be fast, since I have to look up around 500 every 2 seconds (more or less).
Now that we know it is a tiled plane: A simple solution would be two sorted arrays - one for the X-axis intervals, one for the Y-axis intervals. Then do two searches using std::lower_bound. Expected complexity log n for each search. It would be hard to do better and this code would be so simple and rely so much on the already tested std::sort and std::lower_bound you'd only need to look at it again if performance testing showed it to be a bottleneck.
And ... if you got those 500 in a batch every 2 seconds ... sort them too (twice: once on x and then on y) then search in sorted order using the lower bound of each item to reduce the number of items searched for the next item ... though really, now we're talking about an optimization that should only be tried after you determine you have a performance problem.
As to the data associated with each rectangular region of the plane: Create a 2-D array of pointers to that data, indexed by the x- and y-indexes you got back from std::lower_bound. Expected complexity of access into the 2-D array: constant.