<分区>
假设我有一个二维间隔网格。一组沿 x 轴和沿 y 轴的间隔。现在我必须确定一个新对象在 x 轴和 y 轴上属于哪个区间。假设一个新对象有数字，一个是 x 坐标，另一个是 y 坐标。通过确定对象适合的 x 和 y 区间，我想检索一些存储的数据。
我想到了类似 std::map<IntervalX, IntervalY, DataToStore> map 的东西或 std::multimap<IntervalX, IntervalY, DataToStore> map .关于如何实现这一点的任何建议，以便检索间隔对的存储数据非常有效/快速，而不是在 O(n²) 中.
编辑: 间隔由两个浮点值确定。例如:沿 x 轴的区间 [0.5, 3.0)。因此 0.5 包含在内，3.0 将不包含在此区间内，但包含在正 x 方向的下一个区间内。
间隔是不相交的，既不重叠也不嵌套。区间的并集是直线的某个完整段。我确实将平面平铺在一组矩形中，我想知道该点落在哪个矩形区域中。
例如:沿 x 轴的间隔从 0 到 10，间隔大小为 0.5，沿 y 轴的间隔从 2 到 15，间隔大小为 1.0。给定点 P(x=0.7,y=3.0) 它落在哪个区间？它是 x 轴上的间隔 2 和 y 轴上的间隔 2。现在我需要检索为该间隔对存储的数据。
在我的用例中，我将沿每个轴有大约 10000 个间隔，并且必须快速确定对象的间隔，因为我必须每 2 秒(或多或少)查找大约 500 个。