有界线集合相交的高效算法

Question

我有一组配对数字，需要有效地找到包含给定值的一组数字。

给定以下数字对的表示

public class Line
{
    public double Start { get; set; } //is always < end
    public double End { get; set; }
}

集合Lines可以直观地布局如下（黑线）

垂直的红线是交集标准（只是一个简单的数字，如 10.123）

我正在寻找一种有效的算法，基于搜索执行频率大于向Line集合添加的频率的假设，该算法仅返回与红色相交的黑线。（显然假设集合很大）

到目前为止我的不太理想的解决方案是

1. 将创建的行插入两个排序列表中。一个按 排序Start，另一个按 排序End
2. 在起始有序列表上进行二分搜索，查找起始大于交集条件的第一行的索引。（理论上，包括该索引及其之后的所有线都是不相交的）
3. 对最终有序列表重复 (2) 中类似的逻辑
4. 比较索引并选择剩余迭代次数最少的列表进行解析
5. 手动迭代所选列表的其余部分以查找交集

Answer 1

您的Line班级代表\xe2\x84\x9d中的一个区间。您有大量这样的间隔，并且希望在比线性时间更好的时间内找到与某个点重叠的间隔。

\n\n

满足您的要求的一种可能的解决方案是区间树：

\n\n

\n
• 查询需要O(log n + m)时间，其中n是间隔总数，m是与找到的查询点重叠的数量。
\n
• 施工需要O(n log n).
\n
• 存储需要O(n)空间。
\n

\n\n

Codeplex的示例实现（我尚未测试）。对于其他人，请参阅C# Interval 树类。

\n\n

有关与相关结构线段树的比较，请参阅线段树、区间树、二叉索引树和范围树之间有什么区别？。

\n