用于有界线集合的交叉的有效算法

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

给出数字对的以下表示

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

Lines的集合可以像下面那样在视觉上布局（黑线）

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

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

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

1. 将行创建时插入两个排序列表。 一个在Start排序，另一个在Ended上排序
2. 二进制搜索起始有序列表，以查找起始大于交叉标准的第一行的索引。 （理论上所有包括和在此指数之后的线都是非交叉的）
3. 在（2）中对最终有序列表重复类似的逻辑
4. 比较索引并选择要解析的剩余迭代次数最少的列表
5. 通过手动寻找交叉点迭代所选列表的其余部分

Answer 1

Line类表示ℝ的间隔 。 您有大量此类间隔，并且希望找到与线性时间相比优先于某一点重叠的间隔。

一个可能的解决方案是间隔树 ：

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

Codeplex的示例实现（我没有测试过）。 对于其他人，请参阅C＃Interval树类 。

为了与相关结构（ 段树）进行比较 ，请参阅段树，区间树，二叉索引树和范围树之间的区别是什么？ 。

Answer 2

这可能是由两个平行的搜索者完成的，但……
既然你已经管理了两个列表，试试这个：

搜索第一个ValuePoint值> ValuePoint 。
（超出此索引的所有值都明显无效）

 int idx_start = Lines.FindIndex(x => x.Start > ValuePoint); 

通过[.End]的值将列表排序到此点
鉴于您的列表已经排序，此排序永远不会是O（n）操作，
应该平均为O((i) log (i)) ，其中i = Index找到的第一个值的i = Index 。
当然， i可能是= n

 EndComparer ecomp = new EndComparer(); Lines.Sort(0, idx_start, eComp); 

其中EndComparer ：

 public class EndComparer : IComparer { public int Compare(Lines lineX, Lines lineY) { return lineX.End.CompareTo(lineY.End); } } 

然后找到第一个.End值> ValuePoint

 int idx_end = Lines.FindIndex(0, idx_start, x => x.End > ValuePoint); if (idx_end > -1) { //All values in the range [idx_end; idx_start] are valid //If idx_end = 0 then all pre-selected values are valid [0; idx_start] } else { //All value in the range are non valid }