梯形图-清华大学.PDF

梯形图 1. 问题背景 平面点定位是计算几何中的一类经典问题，其研究的目标是通过对平面子区域的预 处理，使我们能够快速获得平面上特定点所处的位置。在许多不同的场合中，都会遇到 类似点定位查询的问题。例如，我们有一张电子格式的航海地图，希望利用计算机来帮 助确定方位。这样，无论何时何地，计算机都能够动态地显示出现在所处位置的水流情 况。在这种情况下，我们可能会拥有一套相当详细的专题图，我们希望能够频繁地进行 点定位查询，从而在航行的过程中，不断地更新显示当前信息。这就意味着，我们希望 对航海图进行与处理，然后将有关信息组织为某种数据结构，从而使得点定位查询可以 很快完成。 点定位问题可以出现在不同的领域。假设我们想要实现一个通过屏幕显示地图的交 互式地理信息系统。用户只要用鼠标点击某个国家，就可以查阅该国的信息。随着鼠标 在屏幕的不同位置之间移动，该系统应该能够始终提供鼠标所在国家的名称。显然，对 于屏幕上所显示的那张地图而言，这就是一个点定位问题；在这里，鼠标的位置就相当 于查询点。这类查询进行的频率很高，毕竟，我们希望能够实时地更新屏幕上的信息。 因此，这种查询必须很快得到回答。这样，我们就再次需要借助某种数据结构，来支持 这种快速的点定位查询[1]。 为了解决该问题，人们从子区域的每个顶点出发引入一条垂线，引入的垂线、原子 区域的边以及设定的矩形区域外边共同组成了该区域的梯形图 （如图1 所示），梯形图 组成的任意子区域均为原区域的一个细分。通过对梯形图的数据结构存储（如图2 所示）， 实现对平面点的快速精确定位。在本次试验中，我们将实现梯形图的构造，通过查询结 构实现点的定位，并对实现的过程进行实验分析。 图1 梯形图 图2 梯形图查找结构 2. 系统设计 2.1 开发环境 Windows XP + Visual studio 2005 。 2.2 编译与链接 工程中使用了MFC+OpenGL 进行开发。 2.3 总体框架 系统主要分为三大模块： ① 系统框架模块 这部分是整个程序框架，负责数据的输入及输出，与其余两大模块进行连接发， 完成所有控件操作。 ② 核心算法模块 这部分主要实现核心算法，对输入线段集构建梯形图和有向无环图的查找结构， 并将结果返回给系统。 ③ 图形绘制模块 这部分主要完成图形界面的绘制，实现对算法结果的图形演示。 3. 数据结构 3.1 基本数据结构 3.2 DCEL 数据结构 3.3 梯形图数据结构 3.4 查找结点数据结构 4. 算法介绍 本实验采用了随机增量式算法实现梯形图。该算法逐一加入各条线段，每增加一条线段 都相应的更新梯形图，并构造出所需的数据查找结构。同时，为了克服算法中因线段引入次 序导致的算法性能不均，在线段次序选择上采用了随机化方法。 4.1 随机增量式算法 对任意一组线段S，通过逐一引入各条线段，为任意一组线段S,构造出对应的梯形图T(S) ， 同时构造出点定位所需的数据查找结构D 。通过随机增量式算法构造出的数据查找结构D ， 为一有向无环图（directed acyclic graph-DAG ），其中有唯一的根结点，同时对应于线段集S 的梯形图中的每个梯形，有且仅有一片叶子。每个内部节点的出度都是2 。所有内部节点分 为两类：x 节点和y 节点。每个x 节点都被标记为S 中某条线段的一个端点；而每个y 节点 都被标记为某条线段。 在对点q 进行查询时，要从根节点出发，沿着某条有向路径到达某匹叶子。最终到达的 那匹叶子，就对应于T(S) 中包含q 的那个梯形。 算法描述： 输入：一组n 条互不相交的线段 输出：梯形图T(S) ，以及与之对应的、限制于一个包围框之内的查找结构D 1、构造一个包围框R ，大小足以容纳全部线段S。初始化梯形图结构T 为包围框R 本 身，