基于DCEL数据结构与增量算法的平面Delaunay三角剖分

下载：程序与文档

1介绍 2

1.1选题背景与意义 2

1.2问题定义 2

1.2.1三角剖分 2

1.2.2 Delaunay三角剖分 2

1.2开发环境 2

1.3小组分工 2

2 DCEL数据结构 3

2.1DCEL的组成 3

2.2 DCEL的实现 4

3 Delaunay三角剖分 4

3.1 基于Graham Scan的凸包算法 5

3.2 基于增量法的Delaunay三角剖分 5

4程序演示 5

4.1程序启动与初始化 5

4.2 Delaunay三角剖分 9

4.3定位演示 11

4.4外接圆测试 12

4.5 DCEL结构测试 13

5参考文献 14

1介绍

1.1选题背景与意义

点集的三角剖分问题是指如何把一个散点集合剖分成不均匀的三角形网格。点集的三角剖分，对数值分析以及图形学来说，都是极为重要的一项预处理技术。Delaunay三角剖分是一种特殊的三角剖分，它具有特殊的性质和重要的应用，是计算几何的一个经典问题。

1.2问题定义

1.2.1三角剖分

三角剖分  假设V是二维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段, E为e的集合。那么该点集V的一个三角剖分T=(V,E)是一个平面图G，该平面图满足条件：

a.除了端点，平面图中的边不包含点集中的任何点。

b.没有相交边。

c.平面图中所有的面都是三角面，且所有三角面的合集是散点集V的凸包。

1.2.2 Delaunay三角剖分

Delaunay边  假设E中的一条边e（两个端点为a,b），e若满足下列条件，则称之为Delaunay边：存在一个圆经过a,b两点，圆内(注意是圆内，圆上最多三点共圆)不含点集V中任何其他的点，这一特性又称空圆特性。

Delaunay三角剖分  如果点集V的一个三角剖分T只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分。

1.2开发环境

基于C++语言，使用了OpenCV2.3与Qt4.7，基于Windows平台VS2010进行开发与测试。

1.3小组分工

**：主要算法的实现与结果的测试。

***：用户界面的实现。

**：资料搜集与文档书写。

2 DCEL数据结构

DCEL数据结构包含了三种对象：顶点、半边和面。这些对象中的元素都是一些指向其它DCEL对象的“指针”。“指针”既可以是C/C++语言中存放内存地址的变量，也可以是句柄、数组的索引等表示地址的类型。这样设计的数据结构非常明显的一个性质就是可以通过指针直接访问DCEL的各种对象。

2.1 DCEL的组成

下面分别介绍DCEL所包含的三种对象。

顶点  顶点对象里仅包含一个变量，即一个指向半边对象的指针。该指针所指向的半边对象以该顶点为起点。当不止有一条半边以该顶点为起点时，顶点对象里的指针可以指向任意一条以该顶点为起点的半边。

半边  半边包含有四个指针变量。第一个指针指向一个顶点的对象，该顶点是这条半边的起点；第二个指针指向一个面对象，该面在这条半边的左边；第三个指针指向一个半边对象，它与这条半边组成完整的一条边；最后一个指针指向另外一个半边对象，它的起点是这条半边的终点，可以看作是这条半边的下一条半边。通过最后一个指针对象可以遍历一个面的所有半边。

面  面对象仅仅包含一个指向半边对象的指针。该指针可以指向任意一个以这个面为它的面的半边对象。

DCEL结构就是上面三种对象的集合，维护DCEL数据结构就是维护这些对象以及它们之间的指针。图2.1.1是一个DCEL的图示。

图2.1.1 DCEL数据结构

2.2 DCEL的实现

本实验基于C++语言实现DCEL数据结构。原理性的代码如下：

3 Delaunay三角剖分

对于一组输入的点集，首先求出其凸包。再根据凸包上极点之间的对角线将点集划分成若干三角形，再对每个三角形进行增量法Delaunay三角剖分。下面简要介绍Graham Scan凸包算法和增量法Delaunay三角剖分的基本原理。算法流程图示参见图3.1。

图3.1 算法图示

3.1 基于Graham Scan的凸包算法

一组输入的点集，要求其凸包，也就是按逆时针（顺时针）方向求出所有极点。首先找出左下角的点。显然，是一个极点。然后，将所有剩下的点按照与连线与水平线所夹的角度排序，得到。创建一个堆栈，先将入栈。进行如下循环：

最终堆栈里便是逆时针方向的所有极点。

3.2 基于增量法的Delaunay三角剖分

在上一步中，已经根据点集的凸包将点集分成了若干个三角形。对于每个三角形所占的区域，进行如下操作：

找出该三角形区域中的一点，通过增加与所在三角形顶点的三条边将该点加入到剖分中。新加入的三条边可能不满足Delaunay三角剖分的条件，这个条件可以通过外接圆测试来判断。如果条件不满足，则通过边翻转策略使其满足Delaunay三角剖分的条件。

4程序演示

4.1程序启动与初始化

首先启动程序，进入主窗口界面，如图4.1.1。

图4.1.1 程序主界面

程序启动之后，首先要输入测试点集。输入区域的坐标原点在左上角。

本实验提供了两种输入点的方式，分别是手动输入和程序自动随机生成。如果选择手动输入，直接在窗口黑色区域单击鼠标左键，每次单击表示在当前位置输入一个测试点，系统会自动将该位置的颜色置为白色。单击可以置空重新输入。单击可以将输入的点按照一定的格式保存起来，单击可以从文件中读出输入点集。如果手动输入后接着让程序再随机生成一定数目的测试点，则之前手动输入的测试点会被清除。而如果首先采用程序自动生成随机测试点再手动输入的话，先前程序自动生成的点会被保留。如果想让程序自动随机生成测试点集，则点击。图4.1.2、图4.1.3和图4.1.4分别对应手动输入测试点集和自动生成随机测试点集。

图4.1.2 手动输入测试点

图4.1.3 选择生成随机测试点的个数

图4.1.4 随机生成的测试点

4.2 Delaunay三角剖分

点击三角剖分图标，便可对当前的点集进行Delaunay三角剖分。如图4.2.1。剖分出的三角形的边会用黄色线画出。

图4.2.1 对一组手动输入的点的剖分结果

如果还需要在原测试点集里加入新的测试点，点击图标，此时便可以再次手动加入新的测试点。每加入一个新的测试点，便立刻绘制出新的剖分结果。如图4.2.2：

图 4.2.2 新加入测试点后的剖分结果

4.3定位演示

点击后再点击某个剖分出来的三角形，可以将该三角形选择出来。算法随机选择一个面通过翻转查找到点击的面，可以设置刷新时间演示查找过程。在系统中将其三条边变为蓝色以表示选中状态。如图4.3.1：

4.3.1 定位演示

4.4外接圆测试

Delaunay三角剖分的特性之一是对任意一个剖分出来的三角形的三个顶点的外接圆不包含其他顶点。程序提供了外接圆测试功能按钮。当按钮为选中状态时，单击任意一个剖分出的三角形便可以显示出该三角形的外接圆，如图4.4.1。

图4.4.1 外接圆测试

4.5 DCEL结构测试

点击后在三角网格中画一条直线段，则被该直线穿过的三角形依次变为选中状态。点击弹出对话框设置刷新时间。这样可以测试出对DCEL结构实现的正确性。如图4.5.1：

图4.5.1 DCEL结构测试

5参考文献

[1]. 计算几何讲义, 邓俊辉

[2]. L. Guibas and J.Stolfi, Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams. ACM Transactions on Graphics, 1985. 2(4): p. 75-123.

[3]. S.Fortune, A Sweepline Algorithm for Voronoi diagrams. Algorithmica, 1987(2): p. 153-174.

[4]. Lee, D.T.A.S., Two algorithms for constructing a Delaunay triangulation. International Journal of Parallel Programming, 1980. 3(9): p. 219-242.