不规则三角形构网.ppt

（一）角度判别法建立TIN该方法是当已知三角形的两个顶点（即一条边）后，利用余弦定理计算备选第三顶点为角顶点的三角形内角的大小，选择最大者对应的点为该三角形的第三顶点。（1）将原始数据分块，以便检索所处理三角形邻近的点，而不必检索全部数据。（2）确定第一个三角形。（3）三角形的扩展。由第一个三角形往外扩展，将全部离散点构成三角网，并要保证三角网中没有重复和交叉的三角形。其做法是依次对每一个已生成三角形的新增加的两边，按角度最大的原则往外进行扩展，并进行是否重复的检测。2）重复与交叉的检测。由于任意一边最多只能是两个三角形的公共边，因此只需给每一边记下扩展的次数，当该边的扩展次数超过2，则该扩展无效；否则扩展才有效。（二）狄洛尼（Delaunay）三角网狄洛尼三角网是与泰森多边形或者Voronoi图的概念联系在一起的，它有两种方法得到，一种是先构建泰森多边形再连三角网。形成泰森多边形可以用矢量算法，也可以用栅格算法，在形成泰森多边形以后，将每个多边形的参考点与它相邻的泰森多边形内的参考点相连就形成了狄洛尼三角网。另一种方法是根据离散参考点直接形成三角网。?

泰森多边形的计算亦可以通过栅格运算的方法进行，以发生点为中心点，同时向周围相邻八方向做栅格扩张运算（也可以说是一种距离变换），两个相邻发生点扩张运算的交线即为泰森多边形的邻接边，三个相邻发生点扩张运算的交点即为泰森多边形的顶点。泰森多边形作为一种空间插值方法和空间分割方法，可以在许多领域找到用途。二、直接建立狄洛尼（Delaunay）三角网1．点与有向线段的关系2．点与三角形最小外接圆的关系*1）向外扩展的处理。若从顶点为的三角形之边向外扩展，应取直线与的异侧点。直线方程为若备选点P之坐标为，则当时，与在直线的异侧，该点可作为备选扩展点。一、由泰森多边形（Voronoi）图形到狄洛尼三角网设有一组离散点，从中取出一个点作为起始点，（例如）从附近的参考点中取出第二个点，作它们两点之间的垂直平分线。然后再垂直平分线附近寻找第三个点，作第i点与前两点的垂直平分线，并相交于前面的垂直平分线。递归下去，找第四点，并作它与前三点的垂直平分线，一直循环下去，这些垂直平分线形成了Voronoi图的边即泰森多边形，根据泰森多边形的性质，每个泰森多边形内仅有一个参考点，将这些参考点连起来即形成了狄洛尼三角网。1．点与有向线段的关系有向线段ab由起点a和终点b确定，点P位于ab的左侧。一般地，令c的坐标为，则c永远位于ab的右侧（ab为水平或垂直矢量时除外）。设ab的直线方程为：，我们有如下点与有向线段关系的判别准则：2．点与三角形最小外接圆的关系点a、b、c确定的的最小外接圆圆心为d，如果点P位于该外接圆的范围内，则P到d的距离小于圆上任意一点到d的距离，因此确定点与三角形最小外接圆的关系这一问题的核心是计算圆心d的坐标。Delaunay三角网生成的基本思路1）确定点集中距离最近的两个点（a,b）,以此边ab为基础，点集被划分为两个子集；2）分别在ab左侧的点集和右侧的点集寻找一个点c和d，使左侧点集中的其他任何点都位于Δabc的最小外接圆外，右侧点集中的其他任何点都位于Δabd的最小外接圆外；3）Δabc和Δabd构成Delaunay三角网的初始生成内核，边ac，cb，bd，da构成该内核的外围边，按顺时针方向给外围边编码；4）始终沿着内核区域的外围边界按顺时针方向逐边考查，直到所有的边的左侧都满足条件的点。*