平面点集三角剖分.PDF

平面点集三角剖分 triangulation of planar point sets 1. 问题背景 计算机在石油、矿山和城市地质等地学领域的广泛使用,使得对三维地学信 息系统的需要更加迫切。雨量等值线在水文、防汛领域应用广泛，Delaunay三角 剖分具有空外接圆和最走的最小角度两个良好性质，对于非规则分布的离散点数 据进行三角剖分内插是生成等值线的最常用的算法，但实际应用中往往都不是凸 壳进行三角化，而是有限定边(或限定点)对三角剖分进行约束。 三角剖分是计算机辅助几何设计、几何造型及计算机图形学中研究的重要内 容之一。对于设计一个三角剖分算法来说,最重要的就是其复杂度低和高质量网 格的形成。三角剖分算法在计算几何、曲面重构及有限元网格生成中有着重大的 应用价值。 对于无限定条件的三角剖分，其剖分方案无确定性，无论对点集做怎样的剖 分，效果都似乎差不多，我们所需要考虑的更多的是算法的复杂度和运行的成功 率。然而，就其外观的自然性和布局的合理性而言，某些三角剖分的确更好。特 别是对于那些给予了约束条件的情况，三角剖分的方案比较有限，比如最小夹角 和条件或者最短路径条件等等。这时，我们就需要采取某些特定的算法来实现， 比如Delaunay 剖分或是贪心算法。 本次实验我们基于分治策略，利用DCEL结构对平面的散乱点集实现了三角 剖分。主要考虑分治的合理性以及算法的时间复杂度问题。 2. 算法及原理 Divide：按点的x坐标的中值（或先按点的二坐标分类，然后从中间分割）分割 点集S为S1和S2，使S1与S2包含的点数近似相等。如果，S1与S2点的数目大于k （k为设定的常数），则继续分割点集，直至点集规模小于或等于k。对每个点集 按照增量算法求其三角剖分。 Merger：对于已经三角剖分过的子点集，由于其外围边界构成凸壳，故而相邻的 子点集间的合并可采用与凸壳合并相似的处理方法。具体操作如下：遍历两凸壳 上顶点连线u1u2与下端点连线v1v2间的所有点；找出其间D1的最右点Pi和D2的最 左点Pk，连接PiPk；从Pi开始与Pk上方的各点连线，使得与凸壳的边界无交点方 止；从停止点仿照上述步骤向P1各点连线，如此往复直至将PiPk与U1U2间的区域 完全三角剖分；自PiPk 向下的三角剖分与之类似。示意图如下 ： D1 D2 图1 3. 系统设计 本次实验，我们基于Visual studio 2008 c# 工作平台编制。在输入端，设 计了三种输入方式，手动输入，文件输入和随机生成。手动输入便于验证算法的 普遍性，文件输入则对于某些特殊的情形给予了演示，随机生成方便演示于用户。 4. 实现过程中遇到的问题及解决对策 实现过程中有很多简单的细节问题，这里就不赘述了。这里说明一下算法程 序经常需要注意的问题。 (1)DCEL数据结构如何具体实现。DCEL只是一种逻辑上的数据组织形式，在 使用时的具体实现我们按照它的基本结构，分别设计了VerTex、Face和HalfEdg 三个类，作为点、面和半边的类型。三个类的如下示： class VerTex //点类 { private Point startPoint; private HalfEdge edge; public Point StartPoint// 点坐标 { get { return startPoint; } set { startPoint = value; } } public HalfEdge Edge // 以该点为起点的有向边 { get { return edge; } set { edge = value; } } public VerTex(Point StartPoint, HalfEdge Edge) { startPoint = StartPoint;