2

我在谷歌上搜索了一下这个主题，并在http://www.geeksforgeeks.org/上找到了这个

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

现在我的问题实际上分为两部分：

  • 如何使用区间树在计算机地图上查找所有道路？
  • 区间树的实际应用还有哪些其他示例？

PS：欢迎参考更多关于区间树的阅读材料进行简要说明

4

2 回答 2

3

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

范围树是一种有效的数据结构，用于查找范围/矩形中存在的点集。因此它们可用于查找所有线段，使得每个线段的端点之一出现在查询 Rectangle 中。这些对应于下图中的蓝色线段。

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

在此处输入图像描述

在解决这个问题之前，想象一个更受限制的问题版本，其中所有线段都是水平或垂直的。在这种情况下，与矩形相交的任何水平线段都应与矩形的左（和右）垂直边缘相交。如果我们将水平线段视为区间，将矩形的垂直边缘视为一个点，那么问题就是要找到包含该点的所有区间。因此我们可以使用区间树来解决这个问题。同样，我们可以找到所有相交的垂直线段。

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

于 2015-04-16T03:58:28.830 回答
1

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

封闭区间搜索问题： 给定一组包含 n 个区间的 S 和一个查询点 q，报告所有包含 q 的区间。

重叠区间搜索问题： 给定一组包含 n 个区间的 S 和一个查询区间 Q，报告 S 重叠 Q 中的所有这些区间。

参考（也与其他类似的数据结构如段树比较）：http ://www.iis.sinica.edu.tw/~dtlee/dtlee/CRCbook_chapter18.pdf

于 2015-10-25T22:57:22.727 回答