查找所有重叠一点的时间间隔

本文介绍了查找所有重叠一点的时间间隔的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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".