平面点集的三角剖分实验报告

目录

一、        问题描述（摘自网络学堂workhard组）：... 2

二、        算法描述：... 2

1.    数据结构设计... 2

2.    递归程序的伪代码：... 3

3.    算法正确性的证明... 4

三、        用户手册... 5

1.    图形界面：... 5

2.    界面操作：... 6

3.    数据输入：... 6

4.    平面点集三角化... 6

5.    DECL数据结构测试... 7

四、        算法测试... 7

五、        存在问题... 7

1.    算法存在问题... 7

2.    程序存在问题... 7

六、        参考文献... 8

一、      问题描述（摘自网络学堂workhard组）：

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

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

2.   有相交边。

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

二、      算法描述：

1.      数据结构设计

根据DECL数据结构，我们设计了以下数据结构来表示点集以及三角剖分的结果。

Vertex类：表示平面中一个顶点

数据成员

说明

double x;

顶点的横坐标

double y;

顶点的纵坐标

Halfedge* edge;

指向顶点的半边指针

Halfedge类：表示平面内的一条半边

数据成员

说明

Halfedge* next;

同一个面内的下一条半边

Halfedge* prev;

同一个面内的上一条半边

Halfedge* twin;

表示同一条边的相反的半边

Vertex* origin;

半边出发的顶点

Facet* facet;

半边所在的面

Facet类：表示平面内的一条半边

数据成员

说明

Halfedge* edge;

面内的一条半边

Mesh类：封装了所有的顶点，面和半边

数据成员

说明

vector<Vertex*> arrayVertex;

所有的顶点

vector<Halfedge*> arrayHalfedge;

所有的半边

vector<Facet*> arrayFacet;

所有的面片

vector<Facet*> arraySelectedFacet;

选择出的面片

vector<Halfedge*> outerBoundary;

外边界的一条半边

2.      递归程序的伪代码：

RunTriangulation(int left, int right)

1.   if(right – left < 3)

2.   trivial processing;

3.   return;

4. else

5.   RunTriangulation(left, (left + 1) / 2);

6.   RunTriangulation((left + 1) / 2 + 1, right;

7.   ZigZagDown(left, right)

8.   ZigZagUp(left, right)

ZigZagDown(int left, int right)

1. a = (left + right)/2, b = a + 1;

2. while(ba is not low tangent of a and ba is not low tagent of a)

2.      add_edge(ba), add_edge(ab)

3.      while(ba is not tangent of a)

4.         do  c = CW_Next(a)

5.            add_edge(cb), add_edge(bc)

6.            a = c;

7.      while(ba is not tangent of b)

8.         do  c = CW_Next(b)

10.           add_edge(ca), add_edge(ac)

11.            b = c;

3.      算法正确性的证明

1.   平凡情况：当点集只由两个或者三个点组成的时候，是平凡情况。只需将所有点按照DCEL规定的方向链接起来即可。具体操作请参考代码中的注释。

2.   递归证明：假设left_set以及right_set都已经递归地三角剖分完毕。下面只需证明归并步正确-即ZigZagDown算法和ZigZagUp算法都是正确的。这个算法的正确性由文献【1】中94页Lemma3.8.2可知，新添加的边cb与ca均不与之前的任何边相交。故合并之后所有三角化已经形成，并且边与边之间没有交点。

3.   综上所述，证明了算法的正确性。

三、      用户手册

1.      图形界面：

为了方便的表示点云的位置，增强现实效果，我们设计了整洁方便的显示界面界面和界面操作。图形界面如图1所示：

主界面中的界面元素如下，在【显示】菜单中可以选择是否显示这些界面元素。

1.   显示框：定位了显示平面点集的核心区域

2.   坐标轴：定位了实际坐标系中原点和X轴，Y轴的位置

3.        网格和刻度：更方便定义点的实际坐标

在状态栏中，用户可以方便的看到点集的信息、当前鼠标的屏幕位置和实际位置，以及用户操作的状态等信息。

2.      界面操作：

放大：程序提供了两种放大操作。第一种，在显示框中滚动滚轮，程序将以当前鼠标所在位置为中心进行放大和缩小操作；第二种，单击【显示】菜单，选中【放大】菜单项，状态栏提示“局部放大：开启”，此时在屏幕上拖动鼠标，程序将绘制选择框，鼠标弹起时，选择区域会放大到显示框中。

恢复：选择【显示】菜单，单击【恢复】按钮，可以使显示框显示整个点集，同时，滚动滚轮也可方便的实现恢复操作。

移动：在显示框显示局部数据时，如果没有选中【放大】菜单项和【Stabbing Query】菜单项，拖动鼠标将会移动点集数据。

3.      数据输入：

程序提供了三种数据输入方式，分别为：

读入文件：单击【文件操作】菜单，【载入文件】菜单项，弹出读取文件对话框，选择所要读入的文件。如果文件合法，程序将显示所读入的点集数据。

随机生成点：单击【平面点集】菜单，【随机生成】菜单项，程序弹出随机生成点集对话框，用户输入随机生成的点集数目和点的坐标范围，程序将随机生成点集数据并在显示框中显示。

手工输入点：单击【平面点集】菜单，选中【手工输入】菜单项，状态栏提示“手工输入状态：开启”。此时用户在显示框中单击鼠标，程序将在屏幕坐标对应的实际坐标位置生成一个点，并添加到平面点集中。

清空点：单击【平面点集】菜单，【清空】菜单项，程序将清空界面上所有点，线，面数据。此时，用户可以再次进行数据输入操作。

4.      平面点集三角化

单击【三角剖分】菜单，【三角剖分】菜单项，如果当前屏幕上有点集数据，程序会调用三角剖分算法进行三角剖分，并将结果显示在界面中。

5.      DECL数据结构测试

单击【测试】菜单，选中【Stabbing Query】菜单项，在显示框中拖动鼠标，程序画一条直线，并显示该直线通过的所有的三角面片。

四、      算法测试

为了比较不同点集的三角网格剖分的执行效率。我们分别随机生成100，1000，10000，100000，500000，1000000个平面点集进行测试。测试结果如下：

点集数目

执行时间（秒）

存储空间（MB）

1000

0.00349353

6.98

10000

0.034546

8.94

100000

0.359465

33.08

500000

2.09345

137

1000000

4.14622

256

2000000

9.26544

542

五、      存在问题

1.      算法存在问题

1 在实现算法的过程当中主要遇到的就是DCEL数据结构的操作问题。由于对于DCEL数据结构不是很熟悉，我们在做相关的操作时犯了很多错误。比如说寻找某一条边的CW和CCW的下一条边界边的时候，总是无法正确的定位到边界边。

2 一个比较常见的问题就是共线的问题。我们在算法当中的toleft测试中做了相关修改，使得可以正确处理共线的问题。

3 另外一个比较常见的问题就是有重复点的问题。我们在算法中的排序之后加入了重复点的判断和去除。

2.      程序存在问题

程序显示效率较慢，特别是当点数很多时，显示的时间已经超过了算法执行的时间。此时，观察算法的执行效果会特别慢，不能满足要求。

3.            经验教训

1.      初期没有进行有效的单元测试，攒了很多的bug，增加了后期的调试难度。

2.      初期没有有效的设计程序框架没，使得后期整合每个人的代码的难度大大增加

3.      团队配合问题。尤其是阅读别人代码的能力。此外要协调好大家的时间，进行有效的交流。

六、      参考文献

【1】Computational Geometry in C (2nd ed). Joseph O’Orurke