查找所有重叠一点的时间间隔 [英] Finding All Intervals That Overlap a Point

问题描述

请考虑一维的大量浮点间隔，例如
。

Consider a large set of floating-point intervals in 1-dimension, e.g.

 [1.0, 2.5],                1.0 |---------------|2.5

 [1.5, 3.6],                      1.5|---------------------|3.6

 .....

希望找到包含给定点的所有间隔。例如，给定点= 1.2，算法应返回第一个间隔，如果给定点= 2.0，则应返回上例中的前两个间隔。

It is desired to find all intervals that contain a given point. For example given point = 1.2, algorithm should return the first interval, and if given point = 2.0, it should return the first two interval in the above example.

我正在解决的问题是，此操作需要以大量间隔重复多次。因此，不希望使用暴力搜索，而性能是一个重要因素。

In the problem I am dealing, this operation needs to be repeated for a large number of times for a large number of intervals. Therefore a brute-force search is not desired and performance is an important factor.

搜索之后，我看到在以下情况下使用间隔跳过列表可以解决此问题：计算几何。我想知道是否有任何简单，有效的C ++实现。

After searching about it, I saw this problem is addressed using interval skip list in the context of computational geometry. I was wondering if there is any simple, efficient C++ implementation available.

编辑：为了更准确地说明问题，有N个间隔，对于M个点，应该确定哪个间隔包含每个点。 N和M是大数，其中M大于N。

To be more precise about the problem, there are N intervals and for M points, it should be determined which intervals contain each point. N and M are large numbers where M is larger than N.

推荐答案

建议使用 CGAL范围树：

维基百科说间隔树（一维范围树）可以有效地找到与任何给定间隔或点重叠的所有间隔。

Wikipedia says interval trees (1-dimensional range trees) can "efficiently find all intervals that overlap with any given interval or point".

这篇关于查找所有重叠一点的时间间隔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！