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

Question

是否可以有效地计算数轴上与单个点重叠的线段的数量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树。

Answer 1

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

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 点要好得多（显然，初始排序会花费一些时间。但您只需要执行一次）。