摘 要

在惊醒计算机图形设计时，通过给定或者随机选取的离散点，构建包含这些点的凸包多边形是我们经常碰到的问题。现如今，对于多个有限个数点的凸包多边形的构建算法已经有了较为广泛的发展以及应用。本次毕业设计即是在教学基础之上，通过对不同算法的优劣选择，在择优的基础上写出对离散点群凸包多边形的生成算法，并且通过编程来实现凸包多边形的生成。本文主要建立通过鼠标交互式操作给出随机点，在窗口显示凸包多边形的算法系统。

本文主要在VS2012构建实验平台，主要通过Graham扫描法进行凸包多边形的构建。

关键词：凸包 离散点群 Graham扫描法 C 编程

ABSTRACT

In the design of computer graphics, it is a problem we often encounter to build a convex polygon containing these points through a given or randomly selected discrete point. Now, the algorithm for the construction of convex polygons for a number of limited number points has been widely developed and applied. This graduation design is teaching. On the basis of the study, by choosing the advantages and disadvantages of different algorithms, the algorithm for generating convex polygons of discrete points group is written on the basis of the optimal selection, and the generation of convex polygons is realized by programming. This paper mainly establishes an algorithm system of displaying convex polygons at the window by the interactive operation of the mouse.

In this paper, the experimental platform is constructed in VS2012, and the convex hull polygon is constructed by Graham scan method.

Keywords: concave bag；discrete point group；Graham scan method；C programming

目录

第一章 绪论 1

1.1 研究背景及意义 1

1.2 研究现状 3

第二章 离散点群凸包多边形开发软件介绍 4

2.1 VS2012软件 4

2.2 MySQL软件 6

2.2.1 MySQL概述 6

2.2.2 索引类别 5

2.3 C 语言 7

第三章 Delaunay方法的基本原理 10

3.1 Voronoi图与Delaunay三角网的基本概念 10

3.2 Delaunay的重要性质 10

第四章 三角剖分改进算法 11

4.1 概三角剖分改进算法 11

4.1.1 算法基本流程 11

4.1.2 Graham扫描法求凸包 11

4.2 详细算法描述 12

4.3 程序运行结果 15

第五章 相似算法 18

5.1Jarvis步进算法 18

5.2单调链算法 20

5.3分而治之算法 20

5.4快速凸包算法 21

参考文献 21

致谢 22

第一章 绪论

1.1 研究背景及意义

大多数情况下我们采集到的数据信息都是非常离散的信号，比如多种参数曲线的数字化信号等，依据大规模的加大采样点的数量，这种方法不具备操作性。且计算量也非常的大。但我们可以利用趋势分析插值的办法，这种办法能够使得信号的模型更加的接近最初的信号模型，但是最终全部的离散数据都要采用同一种办法在计算机中组合成一个整体。

三角剖分的目的是要把分散的数据利用组成大量的三角形来实现面化的要求。这是不是就是说我们能够任意的连接三角形？答案是否定的，最终组合成的面或体需要和最初的模型具备很高的相似性。如何使得最后组合成的面或体与最初的模型具备很高的相似性呢？一般情况下，任意的离散点都具备其自身的作用区间，因此我们在进行组合三角形时，就要做到使得三角形内的点每一个都离得比较近。

这里有两个准则：首先，组合的三角形不应该相互重叠；其次，新的顶点不应该继续出现。

还有面化或者体化时要不要分析边界方面的麻烦？即是不是需要分析边界离散点的凹凸判定，假如需要分析的话，全部的边界点都要顺序的连接，假如不需要分析的话，全部的边界点只要连接就可以。一般情况下是需要进行分析的。而且，面化或体化时要不要分析其内部的空洞的相关领域？即要不要研究内部空白区相关的判定。如果把任意的很多点给你，利用怎样的思路实现三角剖分呢？

先简单后困难，我们能够利用四个点的逆序排列来断定，很明显只存在两种方式（ABC amp; CDA）或者（DAB amp; BCD），假如我们利用空外圆特征进行断定的话，这个问题就变成：

第一种划分需求：点D在三角形的外面 amp; 点B在三角形的外面。

第二种划分需求：点C在三角形的外面 amp; 点A在三角形的外面。

无论上面哪种成立，我们就使用哪种进行三角剖分。

假如依据前面的思路，当点数变多时，我们在进行三角剖分时就很可能碰到大规模的计算问题，这就说明我们的思路存在一定的错误，尽管是依据Delaunay三角网的判定准则，但是并未找出相关的规律。换种想法：首先这样考虑，任意在点云中选取一个点，接着在这个点周围再取两个构成相应的三角形，接着顺序判断其它全部的点是不是在这个三角形的外面，假如有在外接圆内部的点，则在这个点的周围再取相应的点构成新三角形，继续判定。假如全部的点都在外接圆外部时，则从这个三角形的各个边开始向外延伸，直到和全部的点连接在一块。显然这种思路比上面的要容易实现的多，但依然存在一定的缺陷，这种思路没有很理性的判断，当进行循环时，全部数据都需要进行遍历，当信息量非常大时，三角形网中的逐点插入算法效果非常的突出，其实际操作步骤如下所示：

1、访问全部的散点，并计算出点的包容盒，当作最初的三角形并如需想应链表中。

2、把全部的散点按顺序加入，在链表中找到拥有效果插入点的三角形，去除其公共边，把对三角形产生影响的所有点都连接在一块，进而实现一个散点的插入过程。

相关图片展示：