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

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 类代表一个 interval在 ℝ .您有大量这样的间隔，并且希望在比线性时间更好的时间内找到与某个点重叠的间隔。

满足您要求的一种可能的解决方案是 interval tree :

• 查询需要 O(log n + m) 时间，其中 n 是间隔总数，m 是重叠数找到查询点。
• 构造需要O(n log n)。
• 存储需要 O(n) 空间。

在 Codeplex 的示例实现(我还没有测试过) .对于其他人，请参阅 C# Interval tree class .

为了与相关结构进行比较，segment tree , 请参阅 What are the differences between segment trees, interval trees, binary indexed trees and range trees? .