我用谷歌搜索了一下这个主题，并在 http://www.geeksforgeeks.org/ 上找到了这个。
Interval tree is mainly a geometric data structure and often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene.
现在我的问题实际上分为两部分:
- 如何使用区间树查找计算机 map 上的所有道路？
- 区间树的实际应用还有哪些其他示例？
P.S:欢迎引用更多关于区间树的阅读 Material 进行简要解释
最佳答案
在加窗查询中，给定一组线段和一个轴对齐的矩形，我们必须找到线段与矩形的交点。这可以通过将区间树与范围树结合使用来解决。
范围树是一种有效的数据结构，用于查找范围/矩形内存在的点集。因此，它们可用于查找所有线段，使得每个线段的端点之一出现在查询矩形中。这些对应于下图中的蓝色线段。
区间树可用于查找那些与窗口重叠但端点在窗口之外的线段。这些是图中的红色部分。
在解决这个问题之前，想象一下该问题的一个更受限制的版本，其中所有线段都是水平或垂直的。在这种情况下，与矩形相交的任何水平线段都应与矩形的左(和右)垂直边缘相交。如果我们将水平线段视为区间，将矩形的垂直边缘视为一个点，那么问题就是找到包含该点的所有区间。因此我们可以使用区间树来解决这个问题。同样我们可以找到所有相交的垂直线段。
使用区间树无法完美解决线段与轴不平行的问题的一般版本。然而，我们可以使用区间树来消除绝大多数不与查询矩形重叠的线段。对于输入中的每个线段，我们构造一个与轴平行的矩形，其对角线是该线段。然后，我们使用矩形的边构建(水平和垂直)区间树。给定一个查询矩形 R，我们首先可以像以前一样找到与 R 相交的所有矩形。对应的线段与R相交的几率很高，可以单独检查是否实际相交。
关于data-structures - 区间树的实际应用，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29653116/