边界线集合的交集的高效算法 [英] Efficient algorithm for intersection of a collection of bounded lines

问题描述

我有一个成对的数字集合，需要有效地找到包含给定值的成对集合.

I have a collection of paired numbers and need to efficiently find the set of pairs which encompass a given value.

给出数字对的以下表示形式

Given the following representation of a number pair

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

Lines的集合可以如下所示(黑线)在视觉上进行布局

The collection of Lines could be visually laid out like the below (black lines)

垂直红线是交点标准(只是一个简单的数字，如10.123)

The perpendicular red line is the intersection criteria (just a simple number like 10.123)

我正在寻找一种有效的算法，该算法仅基于搜索执行的频率大于对集合添加Line的频率的假设，仅返回与红色相交的黑线. (并且显然假设馆藏很大)

I'm looking for an efficient algorithm that returns only the black lines that intersect with the red, based on the assumption that the frequency of search executions is greater than the frequency of Line additions to the collection. (and obviously assume the collection is large)

到目前为止，我的最佳解决方案不是

My less than optimal solution so far is to

1. 将创建的行插入到两个已排序的列表中.一个在Start上排序，另一个在End
上排序
2. 在开始顺序列表中的二进制搜索，以查找开始大于交集条件的第一行的索引. (理论上，包括该索引在内的所有行都是不相交的)
3. 对最终排序列表重复(2)中的类似逻辑
4. 比较索引并选择迭代次数最少的列表即可解决
5. 手动遍历所选列表的其余部分以寻找路口

1. Insert Lines as they are created into two sorted lists. One sorted on Start, the other Sorted on End
2. Binary Search on the start ordered list to find the index of the first line where the start is greater than the intersection criteria. (in theory all lines including and after this index are non intersecting)
3. Repeat similar logic in (2) for the end ordered list
4. Compare indexes and pick the list with the lowest remaining iterations to resolve
5. Iterate through the remainder of that chosen list manually looking for an intersection

推荐答案

您的Line类表示ℝ中的noreferrer>间隔.您有很多这样的时间间隔，并且希望找到比线性时间更好地重叠某个点的时间间隔.

Your Line class represents an interval in ℝ. You have a large number of such intervals, and would like to find those that overlap a certain point in better than linear time.

满足您需求的一种可能的解决方案是间隔树:

One possible solution for your requirements is the interval tree:

• 查询需要O(log n + m)时间，其中<​​c6>是间隔的总数，而m是与找到的查询点的重叠数.
• 构造需要O(n log n).
• 存储空间需要O(n)个空间.

• Queries require O(log n + m) time, Where n is the total number of intervals and m is the number of overlaps with the query point found.
• Construction requires O(n log n).
• Storage requires O(n) space.

Codeplex 上的示例实现(我尚未测试).有关其他内容，请参见 C#间隔树类.

Example implementation (which I have not tested) at Codeplex. For others see C# Interval tree class.

要与相关结构(细分树)进行比较，请参见

For a comparison with a related structure, the segment tree, see What are the differences between segment trees, interval trees, binary indexed trees and range trees?.

这篇关于边界线集合的交集的高效算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！