在 C++ 中实现二维区间搜索的最佳方法是什么？
What's the best way to implement a 2D interval search in C++?
假设我有一个间隔的二维网格。一组沿 x 轴和沿 y 轴的间隔。现在我必须确定一个新对象在 x 轴和 y 轴上属于哪个区间。假设一个新对象有数字，一个是 x 坐标，另一个是 y 坐标。通过确定对象适合的 x 和 y 间隔，我想检索一些存储的数据。
我想到了 std::map<IntervalX, IntervalY, DataToStore> map 或 std::multimap<IntervalX, IntervalY, DataToStore> map 之类的东西。关于如何实现这一点的任何建议，以便检索间隔对的存储数据相当 efficient/fast 而不是 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 个。
如果间隔不重叠（听起来像，因为你说一个点映射到每个轴上的单个间隔），我只是按排序顺序存储它们 max(Interval_n) < min(Interval_n+1) 允许高效的二进制搜索查找。
如果它们确实重叠，您可以按最小值排序，但这只会帮助您一点点。
现在我们知道它是一个平铺平面：一个简单的解决方案是两个排序数组 - 一个用于 X 轴间隔，一个用于 Y 轴间隔。然后使用 std::lower_bound 进行两次搜索。每次搜索的预期复杂度 log n。很难做得更好，而且这段代码非常简单，并且非常依赖已经测试过的 std::sort 和 std::lower_bound 如果性能测试表明它是，你只需要再看一遍瓶颈。
并且...如果您每 2 秒批量获得这 500 个...也对它们进行排序（两次：一次在 x 上，然后在 y 上）然后使用每个项目的下限按排序顺序搜索减少为下一个项目搜索的项目数量...虽然实际上，现在我们正在谈论的优化应该只在您确定您有性能问题后尝试。
关于与平面的每个矩形区域关联的数据：创建一个指向该数据的二维指针数组，由您从 std::lower_bound 返回的 x 和 y 索引索引。访问二维数组的预期复杂度：常量。
假设我有一个间隔的二维网格。一组沿 x 轴和沿 y 轴的间隔。现在我必须确定一个新对象在 x 轴和 y 轴上属于哪个区间。假设一个新对象有数字，一个是 x 坐标，另一个是 y 坐标。通过确定对象适合的 x 和 y 间隔，我想检索一些存储的数据。
我想到了 std::map<IntervalX, IntervalY, DataToStore> map 或 std::multimap<IntervalX, IntervalY, DataToStore> map 之类的东西。关于如何实现这一点的任何建议，以便检索间隔对的存储数据相当 efficient/fast 而不是 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 个。
如果间隔不重叠（听起来像，因为你说一个点映射到每个轴上的单个间隔），我只是按排序顺序存储它们 max(Interval_n) < min(Interval_n+1) 允许高效的二进制搜索查找。
如果它们确实重叠，您可以按最小值排序，但这只会帮助您一点点。
现在我们知道它是一个平铺平面：一个简单的解决方案是两个排序数组 - 一个用于 X 轴间隔，一个用于 Y 轴间隔。然后使用 std::lower_bound 进行两次搜索。每次搜索的预期复杂度 log n。很难做得更好，而且这段代码非常简单，并且非常依赖已经测试过的 std::sort 和 std::lower_bound 如果性能测试表明它是，你只需要再看一遍瓶颈。
并且...如果您每 2 秒批量获得这 500 个...也对它们进行排序（两次：一次在 x 上，然后在 y 上）然后使用每个项目的下限按排序顺序搜索减少为下一个项目搜索的项目数量...虽然实际上，现在我们正在谈论的优化应该只在您确定您有性能问题后尝试。
关于与平面的每个矩形区域关联的数据：创建一个指向该数据的二维指针数组，由您从 std::lower_bound 返回的 x 和 y 索引索引。访问二维数组的预期复杂度：常量。