What’s the best way to implement a 2D interval search in C++? [closed] Code Answer

Hello Developer, Hope you guys are doing great. Today at Tutorial Guruji Official website, we are sharing the answer of What’s the best way to implement a 2D interval search in C++? [closed] without wasting too much if your time.

The question is published on by Tutorial Guruji team.

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).

Answer

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.

We are here to answer your question about What’s the best way to implement a 2D interval search in C++? [closed] - If you find the proper solution, please don't forgot to share this with your team members.

Related Posts

Tutorial Guruji