4

是否可以有效地计算与数轴上单个点重叠的线段P数？

所有线段都位于一条数字线上（它是一个1-D世界，而不是一个3-D世界）。

每条线段都有一个起始坐标X1和一个结束坐标X2。

例子：

Line segment A spans from X1==1 to X2==3
Line segment B spans from X1==2 to X2==4
Line segment C spans from X1==3 to X2==5
Line segment D spans from X1==1 to X2==4
----------------------------------------
Ex1: Line segments that overlap point P==2: A,B and D   >>> overlap count==3.
Ex2: Line segments that overlap point P==7: None        >>> overlap count==0.
Ex3: Line segments that overlap point P==3: A,B,C and D >>> overlap count==4.

当然，如果只有4条线段，那么代码就简单了。但是，如果有一个包含 4 亿条线段的庞大空间数据库，那么搜索就会很慢。

是否有任何算法可以有效地搜索此线段列表中的重叠总数？

到目前为止我在看什么

  • 关于空间索引搜索算法的文章。
  • 区间树（看起来很有希望）。
  • 分段树（看起来很有前途）。
  • R树。
4

4 回答 4

3

如果您按起始值对列表进行排序，然后再次（对于相同的起始值）按长度排序，您最终会得到有效算法的根。

sort the list by starting value
for the same starting value, sort by length (longest first)

然后，当您需要与给定点 P 重叠的线段数时：

for a given value p
find the points in the list with starting value <= p (binary search - fast)
for each starting value, start with the longest length
if it spans the point of interest, increment counter
if not, go to the next smaller start value
keep going until you have reached the smallest starting value

它并不完美，但比搜索 10M 点要好得多（虽然初始排序显然需要一些时间。但你只需要这样做一次）。

于 2013-06-22T19:46:32.180 回答
1

在单个数组中对查询点和区间端点进行越来越多的排序；对于每个点，保留一个标志，告诉它是间隔开始、间隔结束还是查询。

将计数器初始化为零并扫描列表。开始增加计数器；结束减少它；查询通过读取计数器知道重叠间隔的数量。

如果可以使用特殊排序，时间 (N+M).Log(N+M) 或更好。

如果不允许对查询点进行排序，只需对区间端点进行排序。在单个线性扫描中，您可以计算每个端点之后的重叠数。

对于给定的查询点，您可以通过二分搜索找到相关的端点，因此重叠计数。

M.Log(M)+N.Log(M) 用于 M 个区间和 N 个查询点。

如果不允许对区间进行排序，只需对查询点进行排序。

依次处理每个区间，通过二分查找找到它重叠的第一个查询点，并增加它重叠的所有查询点的计数器。

N.Log(N)+M.Log(N)+O 其中 O 是间隔/查询重叠的总数。

如果您根本不允许排序，请针对每个间隔对每个查询进行详尽的测试，NM

于 2016-02-26T15:06:06.087 回答
0

看看区间树或分段树来帮助解决这类问题。这个答案有一些很好的例子来说明这些技术如何帮助你。

于 2016-02-26T14:28:10.367 回答
-1

首先要意识到你不能比 O(N) 做得更好，因为你需要至少查看每个线段一次。（其中 N=线段数）

让我们有一个数组 Line_segments_at，它存储通过每个点的线段数。

首先，我们需要将此数组初始化为 0。然后，当我们查看第 i 条线段时，我们需要执行以下操作：

for(int j=x1[i];j<=x2[i];j++)
 Line_segments_at[j]++;

对于每个查询点 k，我们可以简单地将结果返回为 Line_segments_at[k]。

于 2013-06-22T20:34:48.107 回答