区间树的实际应用

Question

我在谷歌上搜索过这个话题，并在http://www.geeksforgeeks.org/上找到了这个。

区间树主要是一种几何数据结构，通常用于窗口查询，例如，在矩形视口内的计算机地图上查找所有道路，或在三维场景中查找所有可见元素。

我的问题其实有两部分：

• 区间树是如何在计算机地图上找到所有道路的？
• 关于区间树的实际应用，还有哪些其他的例子？

P.S:对于更多关于间隔树的阅读材料的简短解释将是非常欢迎的。

Answer 1

在窗口查询中，给定一组线段和一个轴对齐的矩形，我们必须找到直线段与矩形的交点。这可以通过使用区间树与距离树相结合来解决。

距离树是一种有效的数据结构，用于查找区域/矩形中存在的点集。因此，它们可以用来查找所有的线段，这样每个线段的一个端点就会出现在查询矩形中。它们对应于下图中的蓝线段。

区间树可用于查找那些与窗口重叠但其端点位于窗口之外的段。这些是图中的红色片段。

​

​

在解决这个问题之前，想象一个更严格的问题版本，其中所有的线段都是水平的或垂直的。在这种情况下，与矩形相交的任何水平段都应该与矩形的左(右)垂直边相交。如果我们把水平段看作区间，把矩形的垂直边看作点，问题是要找出包含点的所有区间。因此，我们可以使用区间树来解决这个问题。同样，我们可以找到所有相交的垂直线段。

线段与轴不平行的一般问题不能用区间树完美地解决。但是，我们可以使用区间树来消除与查询矩形不重叠的绝大多数线段。对于输入中的每个线段，我们构造了一个轴平行矩形，其对角线是线段。然后，我们使用矩形的两边构造(水平和垂直)间隔树。给定一个查询矩形R，我们可以像以前一样首先找到与R相交的所有矩形。相应的线段很有可能与R相交，并且可以单独检查实际的交点。

Answer 2

也许不能直接回答你的问题，但我认为这可能会有帮助：

包围区间搜索问题：给出了n个区间的集合S和一个查询点q，报告了所有包含q的区间。

重叠区间搜索问题：给出n个区间的集合S和一个查询区间Q，在S重叠Q中报告所有这些区间。

参考(与其他类似的数据结构(如分段树)比较)：chapter18.pdf