c++ - 查找与点重叠的所有区间

Question

考虑一大组一维的浮点区间，例如

 [1.0, 2.5],                1.0 |---------------|2.5

 [1.5, 3.6],                      1.5|---------------------|3.6

 .....

希望找到包含给定点的所有区间。例如给定点 = 1.2，算法应该返回第一个区间，如果给定点 = 2.0，它应该返回上例中的前两个区间。

在我正在处理的问题中，这个操作需要在大量的时间间隔内重复大量的次数。因此，不需要蛮力搜索，性能是一个重要因素。

在搜索它之后，我发现这个问题是在计算几何的上下文中使用间隔跳过列表来解决的。我想知道是否有任何简单、高效的 C++ 实现可用。

---

编辑：为了更准确地了解问题，有 N 个区间，对于 M 个点，应该确定哪些区间包含每个点。N 和 M 是大数，其中 M 大于 N。

Answer 1

建议使用CGAL 范围树：

维基百科说区间树（一维范围树）可以“有效地找到与任何给定区间或点重叠的所有区间”。

Answer 2

如果您的间隔分布允许，则可能值得考虑网格化方法：选择一些网格大小s并创建一个列表数组。every k-th 列表枚举与 "cell" 重叠的间隔[k.s, (k+1).s[。

然后查询相当于找到包含查询点的单元格（in O(1)）并报告列表中有效包含它的所有区间（in O(K)）。

O(I.L+G)预处理时间和存储都是根据网格大小和网格单元总数I的间隔数和L平均间隔长度。必须谨慎选择。Gs