一个任意的多边形，存在按逆时针顺序的相邻的三个点，P，Q，R,如果det(Q,R,P)≧0，则称Q为多边形的一个凸顶点。如果该多边形所有的顶点都是凸的，则称该多边形是凸多边形，这个凸多边形最外侧边所形成的环形成为该点集的临时边界环（本课题中讨论的是逆时针方向）。对于顶点按逆时针排列的四边形ABCD，如果det(A,C,B）det(A,C,D)<0,det(B,D,A)det(B,D，A)<0同时成立，则称该四边形是凸四边形。

3。2平面散乱点集生成三角网

   所谓平面散乱点集的三角剖分，就是指利用直线将平面离散点连接起来，并且这些直线互不相交，能够确保点集区域中的每一个区域都能被三角形所覆盖。节点，边以及面是构成三角网（ＴＩＮ）的基本元素。节点是用来构建TIN三角网的原始采样的数据值，边是由相邻节点连接而成，由两个相邻三角形所共享，而面是由组成三角形的三条边所构成，是形成三角网的最基本元素。构成三角网的各个三角形互不交叉，参与构建TIN的三角形的顶点，三角形的边，面（三角形）之间存在一定的拓扑关系。文献综述

  3。2。1 理论原理

  三角形是组成三角网的基本单元，因此三角形的形状将会直接影响三角网的质量。由于相关的地形数据间存在很强的相关性，相邻数据之间的关系更为紧密。同时，狭长的三角形的插值精度可信度大幅度下降，因此，在三角网中，对所生成的三角形质量有着严格的要求，概括成以下三个原则：

（１）所生成的三角形最大限度接近正三角形。

（２）是由相邻的三个点形成三角形。

（３）生成的三角形网格需要满足唯一性。

　3。2。2基本准则和相关算法

　　　三角网的三角剖分准则是指平面各个离散点之间用什么法则来生成三角网，选取不同的生成三角网的准则，最终得到的不同的三角形的几何形状，从而影响三角网的质量。目前，在计算机几何学中常用的有下面六种：空外接圆准则，最大最小角准则，张角最大准则，最短距离和准则，面积比准则和对角线准则。

　　 在本课题中，主要用的是空外接圆准则以及最大最小准则。

     另外，三角网的生成算法有很多种，常见的有三角网生长法，逐点插入法以及分治法，都有各自的特点。本课题中采用的是逐点插入法，这种方法特点是思路比较简单，并且易于编程实现。

3。3 Delaunay三角网及其优化算法

一般来说，规则网格之间的拓扑关系更加简单，在复杂的数据分布之间存在着某些不协调性；而不规则的三角网格(TIN)能够较全面地考虑到数据的分布位置和特征，适用于复杂的曲面细节描述。这种结构存在着很小的数据冗余，精度高，速度快，方便操作和计算。本课题使用的是Delaunay三角网的构建。

3。3。1三角剖分

      假设V是平面上的一个散乱点集，边e是由这个点集构成中的点构成的封闭线段。E为e的集合，那么该点集v的一个三角剖分T=（v,e)是一个平面图形G，该平面满足条件:

(1)除了端点，平面图中的边不包含点集中的任何点。来;自]优Y尔E论L文W网www.youerw.com +QQ752018766-

(2)任意两条边都不相交。

(3)平面图中的所有的面都是三角形，并且所有的三角面的合集构成了平面散乱点集v的凸包。

在实际应用中，一般用的最多的是Delaunay三角剖分，它是一种特殊的三角剖分。

Delaunay边：假设E中的一条边e,它的两个端点为a,b,e满足下列条件，则称其为Delaunay边，即存在一个圆经过a,b两点，圆内（注意是圆内，圆上最多存在三点共圆),不包含点集v中的其他所有的点，这一特性又叫做空外接圆特性。 OPENCV地形场景的三维重建实现(5):http://www.youerw.com/tongxin/lunwen_94785.html