梯形图算法的实现

1、梯形图算法的实现计算几何实验报告 许振华 李灵坡选题背景平面排列问题是计算机很重要的组成部分，并且有着广泛的应用背景，如GPS等。其基本思想是利用平面上已知的一定数目的曲线排列，将平面划分为一些相互连接的单元，并满足一点的目的。这些单元可以包括点、曲线和面。利用这些单元就可以实现平面映射从而实现相关的应用。点定位问题是平面排排列问题中比较重要而且比较基础的内容，它可以描述为：给定一定数目的曲线，通过一定的处理构建一个数据结构，这样对于给定的任何一点可以有效地找到和这个点对应的单元。实现这个目的有一种很简单的算法就是遍历所有的边和定点，然后找到和要查询的点对应的单元。这种算法不需要任何其他的空间

2、存储，简单方便，但是这种算法的复杂度为O(n)，对于大规模问题来说，查询速度非常慢，而对于普通的查询来说，往往有O(logn)的性能，算法还有很多提升的空间。一种更有效的做法就是将搜索区域按照空间分成垂直的条带状，并对于每个带内部的进行查找，这样在X和Y方向上同时进行二分查找，可以在O(logn)的时间内实现点的查询，只是这种算法需要的空间复杂度为O(n2)。对于这种方法，Snarnack和Tarjan使用优先查找树的结构将算法的空间复杂度降低了许多。本文介绍的算法室友Mulmuley和Seidel基于随机插入构建(randomized incremental construction)思想而

3、提出的，算法将搜索结构分解成一些竖直的梯形，并构建一个有向循环图作为查找结构，其空间复杂度为O(n)，查询的时间复杂度的期望值为O(logn)，在这里我们称之为梯形图算法。算法描述本次实验中的算法针对没有重合的线段排列中的点定位问题进行。依据线段的分布，将空间分成一些点、线段和梯形的集合，并构建与之对应的查找结构。在本算法中每个梯形的图片 1：梯形结构图片 2：平面划分结构如图1所示：有两条线段（或者是搜索区域的边界）构成了梯形的上下边，两个定点所在的竖直线段构成了梯形另外两边。整体的表面划分和搜索结构如图2和图3所示。具体的算法描述可以参见作者论文 R. Seidel. A simple a

4、nd fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Comput. Geom. Theory Appl., 1(1):5164, 1991.。图片 3：搜索结构算法实现本次试验中我们在VC6.0框架下采用MFC对于梯形图算法进行实现和仿真。其中，对于平面图的划分采用DCEL的方式进行存储，并辅助以一个有向循环图进行查找，算法主要包括6中数据结构：Point，Hsegment，Face，Dpoint，Segment和Tra

5、pezoid。其中前三种结构的内容和功能和DCEL结构相同，Dpoint用于存储查找结构的每一个节点，可能包括三种类型：点、线段和梯形。Segment和Trapezoid是辅助结构，用来存储对应的边界点。在查找结构中，每个点类型查询点包含一个指向Point的指针，每个线段类型查询点包含一个指向Segment的指针，梯形类型的查询点Trapezoid结构的指针，这三种指针以联合的形式存放于Dpoint结构内，共用一块内存，具体参见附带源码。算法采用逐步插入更新的方法实现。每一条线段插入后都会生成一个完整的平面划分图和查找结构。每次插入新的线段时，平面划分和相应的数据结构都要进行更新。依据新插入线

6、段和需要更新的梯形之间的关系具体包括一下三种情况：线段在梯形内、线段从一边穿过梯形、线段贯穿梯形，分别采用不同的函数进行处理，具体操作参加邓老师课件06.pl.e.TrapMap，12-14, 2008。在每一步的实现过程中，要使用已经生成的查找表寻找和点对应的梯形，这样每一步的执行都要利用上一步生产的查找结构。本算法实现过程没有利用任何现成代码，所有代码完全由自己编写完成。技术难点和解决在本次算法实现过程中，主要的困难存在于几个方面，对应的问题描述和以及解决方法如下。1. DCEL结构的使用由于DCEL结构已经有很多现成的代码，特别是在CGAL算法库中。在实验初期试图使用现成的DCEL结构进

7、行处理，但是由于在实验中，需要使用的功能相对比较特殊也比较简单，这里重新实现了DCEL结构，并按照自己算法的要求设计了一些特殊的操作函数。由于DCEL是双向连接的机制并且包括三种的结构，在进行函数设计的时候必须同时考虑和当前操作部位相关的所有数据结构的变化情况。在本实验中进行函数设计的时候，本着每次都尽可能的保证所有结构中的数据尽可能完整的原则，对于每一步的更新都更新所有相关的结构，实现了函数功能的鲁棒性。2. 退化情况的处理这里的退化情况主要包括两种，一种是插入的线段为竖直线，另一种为插入的线段的端点和两外线段的端点在共同的竖直线上。对于第一种情况，我们采用的方法是只讲其中的第一个定点作为查

8、找结构的组成部分，第二个点作为辅助点用于判断查询点是不是在对应的线段上。对于第二种情况，如果插入线段的定点在对应梯形的竖直边上（和其它定点在同一竖直线上），就简单的将此定点插入到对应的边上，而不生成新的梯形。这种情况下，对应的定点则不会出现在查找结构里面，而相应的线段则照常显示。在算法的实现过程中，我们将这种特殊情况和标准的情况一起考虑，尽量减少代码的重复性当这两种情况同时出现的时候，也就是竖直线段同时在垂直方向上的时候，则对应的线段对于平面图的划分不产生影响，则无论是线段还是对应的端点都不会出现在查找结构中。只是在对应的DCEL结构中加入相应的点。3. 树结构的显示由于查找结构比较复杂，对于

9、几条线段的查找结构往往就会生成比较长的查找结构，而且对于线段分布比较复杂的情况，同一个梯形可能会有很多个不同的上层地点，这样给查找结构的显示带来和很大的困难。这里我统计查找结构的层数和每一层节点数的方法，计算对应的查找结构显示窗口的大小，从而实现对应的查找结构。为了避免大量的重复节点造成的连接线比较混乱的情况，我们使用树的结构显示对应的DAG，其中相同编号的编号对应相同的查找结构。4. 数据结构的析构由于DCEL是多向的，基本上是以半边为主线，对应的定点和面几乎是挂在半边上的，面和定点之间是一对多的关系，这样容易出现重复删除。由于我们使用C+语言实现，语言本身无法判断对应的内存空间是不是已经被

10、析构，所以很容易因为对同一个位置重复删除而出错。在这里为了避免这种情况，我们采用类似堆栈的形式，每次删除都把和当前顶点对应向连接的新顶点放入到当前堆栈中。每次都从末尾取一个顶点进行删除。同样，对于DAG结构的删除也存在对应的问题，为了避免重复删除，这里采用广度优先的遍历并以一个队列作为辅助结构进行对应空间的析构。5. MFC对MFC界面编程不熟悉是本次实现过程中最大的难题。MFC中各种窗口类名目繁多，WINDOWS各种API也让人眼花缭乱。只能在巨大的信息量中慢慢挑选自己需要的。因此花了很多时间。本次实现过程中主要用到了对话框类和CSCROLLVIEW类。整个应用程序是基于SDI的框架搭建的。

11、a) 对话框类重点用对话框类实现了界面右侧的控制面板。该对话框的父窗口是一个view，当view的OnDraw函数被调用时，该对话框也会随着view的大小和位置调整自己的属性。但是该对话框始终保持在该view的右侧。在这个过程中，主要用到的函数首先是CWnd: :SetWindowPos()，用于最终摆放对话框的位置；其次是CWnd: :GetWindowRect()用于得到view的窗口的位置；以及CDC: :LPtoDP()用于将逻辑坐标转化成设备坐标。b) CScrollView类嵌入对话框中在显示梯形图的树形结构时，原本打算采用的是弹出式的对话框。后来发现梯形图的树形结构非常庞大，小对

12、话框根本容纳不下。于是采用在对话框里嵌入一个CScrollView的方法来显示树形结构。但是CScrollView并不能直接嵌入对话框中，因为初始化view的过程中，需要一个frame做它的父窗口，因此必须先嵌入一个CWndFrame，然后再嵌入CScrollView。否则在显示窗口时，会有一句断言无法通过。另外，也尝试了改变鼠标的样式，用WINAPI :SetCursor()在画线段时将鼠标设置成蜡笔，在删除时设置成红叉。6. OpenGL对OpenGL的使用不够熟练也是本次作业中的一个难题。如果不能熟练使用OpenGL，很多情况下甚至画出来的图形比直接用CDC还要糟糕。本次实现过程中，主要

13、熟悉了OpenGL的 以下几个方面c) 主要熟悉了OpenGL的投影模式和模型视角模式的矩阵的操作。因为本次作业只涉及到了平面上的物体，因此就用了最简单的正交投影模式，用的最多的函数是glortho()。在设置完投影矩阵之后，还需要设置合适的函数进行OpenGL窗口坐标和windows窗口坐标的相互转化。因为windows的窗口坐标是向下为y正方向，左上角为原点，而OpenGL是向上为y正方向，左下角为原点。d) 另外使用了OpenGL的简单的画点，线，多边形的功能。多边形的绘制有三种模式可以选择，用glPolygonMode()如果传入参数GL_FILL，则得到的是实心的完整的多边形；如果传

14、入参数GL_LINE，则绘制得到的是线框的多边形；如果传入参数GL_POINT则绘制得到的是只有顶点的多边形。e) 最后，使用了OpenGL的抗锯齿功能，美化了画出的图形。图片 4：抗锯齿前图片 5：抗锯齿后 实验测试由于数据线段比较多的时候查找结构比较复杂，而且占用空间比较大，这里不太容易显示，这里仅说明简单线段的查找结构(图6、图7)、竖直线比较多的情况下的划分结构(图8)复杂情况的平面划分(图911).。图片 6：平面划分图片 7：查找图图片 8：多种特殊情况的例子图片 9：类切草结构的平面划分图片 10：楼梯结构图像图片 11：随机杂乱线段的结构要进一步完善的工作由于时间和作者能力限制

15、，本实验还有一些问题需要进一步完善，主要包括以下几个方面，这里理出问题的特点和作者的拟解决方法：1. 算法的分步动态演示本程序中算法的分步动态演示是采用了最原始的方法，每一次更新线段之后所有的线段重新计算一次，从而能够及时的更新图形界面。这种实现方法，对于仅仅实现几十条边问题能够很快的实现，如果边的数目过多，则每次重新计算则是对计算资源的严重浪费，因此，因此需要更好的方法进行处理，主要有几种思路a) 每次存储生成的数据结构，对于单步查看的每一步，读取相应的文件并显示。这种方法能够快速的显示算法的过程，但是对于大规模的问题，显然要造成大量的资源浪费b) 每次存储和和上一步有差别的结构，在单步执行

16、的时候读取并更新：这种方法相对上一种方法在时间和空间上都有大量的结余，但是实现起来比较困难，特别是无论DCEL还是DAG都是有循环结构的，在执行的时候需要增加很多辅助函数。c) 动态的删除新生成的结构。每次回退一步的时候，查找上一步生成的新结构并将之删除。这种算法不会造成多余的空间浪费，但是查找每次新生成的空间结构并将其复原的复杂度和梯形图算法本身的复杂度差不多。需要进步不的努力。从整体的对比来看，第二种方法会更有效，但是第三种思路显得更为完美，可以放在以后进行尝试。2. 算法的效能分析由于梯形图算法是期望意义下的O(logn)算法，算法的性能和线段插入的顺序密切相关。不同参数顺序的空间结构都

17、一样，但是查询效率比较低。对于生成的线段，随机生成查询插入顺寻并统计一定数目代表性节点的查询效率，对于理解本算法有比较重要的意义。3. 查找树的动态显示：由于是新手，对于MFC不熟悉，没办法很好的生成一个美观的查找图。由于查找图的结构并不是平衡二叉树，最后生成的图的层数和每一层的节点数都不固定，这样对于查找结构的长宽设置影响很大。由于没插入一层就跟新上一步节点的做法时间复杂度超过了O(n2)，本次实验没有尝试。如何更有效更美观的显示相应的查找结构，仍需要进一步研究。在算法检查之前，算法有五个方面的问题，如下：1. 树形结构很杂乱，无法看清楚2. 图形界面的颜色搭配不够美观，操作不够人性化3.

18、在实现多个跨区域连接和空间释放的过程中容易崩溃4. 不能合适的处理开始是竖直线段的情况5. 没有通过几种特殊数据的测试在后来的实现过程中，我们找出了算法出现问题的原因，并一一进行了改进，最终的结果如当前算法所示。界面操作说明图片 12：实例图像线段为红色线条，梯形图为绿色线条。1. 选择菜单栏的“文件->导入数据”选项，可从txt文件导入线段数据，数据的格式如下segmentNUMsegment1Begin.x segment1Begin.y segment1End.x segment1End.ysegment2Begin.x segment2Begin.y segment2End.x segment2End.ysegment3Begin.x segment3Begin.y segment3End.x segment3End.y参见文件夹中2. 右侧为主要的控制面板