三角剖分

分算法。以上三角剖分算法都只是基于边和三角的形生成，而没有考虑平面中数据点集的生成对剖分的影响。

平面点集的生成会对整个抛分结果产生影响。如图3-1所示，由于A区域中的点过于集

图3-1 示例

中，而其它区域中的点比较分散使得抛分结果中出现了大量的病态三角形。这种病态三角形将会严重影响抛分算法。所以本人针对此缺点对抛分算法进行改进。算法的基本思想是：首先在平面点的提取方面，要尽量保证点集均匀的分布在所抛分的区域，然后在对平面点集进行抛分。

本人在均匀点生成过程中采取密度生成法。如图3-2所示，我们将抛分区域面积除以抛分点个数得到区域A，在插入点时我们将随机生成一个坐标点D，判断以点D为中心以A区域为范围内是否有点存在，如果有点存在那么在D坐标中插入点，如图3-2中D1 点坐标所示在区域A1中没有其它点，所以在D1 点可以插入数据点。如果不存在将重新寻找其它区域插入数据点，如图3-2中要插入D2点在A1区域已经存在D3点那么此区域就不能在插入新点。这种方法可以使数据点均匀的分布在整个区域。

图3-2 示例

3.2算法的具体描述

输入：平面面积S，数据点个数n。 输出：平面中n个点的三角剖分列表L。 具体步骤如下：

步骤1使用平面面积S除以数据点个数n等于单位点最少所需面积Smin。 步骤 2 随机在平面范围内选取一个坐标d(x,y)。

步骤 3 判断以d(x,y)点为中心点，判断在Smin为正方形面积范围内是否存在点。如

三角剖分

果存在执行步骤2，否则继续执行下一步。

步骤 4 将坐标d(x,y)插入D(d1,d2...dk),k<=n（数据点集合）。 步骤 5 执行步骤2直到n个点全部插入D(d1,d2...dk),k<=n

步骤 6 从D(d1,d2...dn)中取出三个不在同一直线上的点d1,d2,d3为待扩展的三角形的顶点，d1d2为待扩展边。

步骤 7 查看d1d2边的使用次数flag=2，返回，如果flag<2，继续。

步骤 8 在点列表D中查找满足条件的点d4，依次从列表中取出点di(i=1,2...n)；执行步骤3时会出现以下几种情况：

1)判断di(i=1,2...n)点是否为三角形的端点，如果是，转步骤3，否则继续。 2)判断di(x,y),i=1,2...n点与d3点是否分别位于线段d1(x1,y1)d2(x2,y2)两侧。这个判断是取决于两个三阶行列式

xx1x2

yy1y2

1

x3

y3y1y2

111

1 与 x11

x2

的值是否同号。如果是同号,表示d与d3位于d1d2的同一侧，转步骤3，否则继续。

3)查看p点的边是否有p1,p2点，如果有其中之一的边使用次数flag=2，转步骤3，如果flag＜2，继续。

步骤9计算d1d与dd2的夹角以及d1d'与d'd2的夹角的角度值，d'为上一次找到的点，如果新生成的角度比上一次找到的点所成的角度小，则在列表D中更新这个值并且记录d点。记录到d点就继续，否则返回步骤3。

步骤10 d点为找到的点，将以d1,d2,d4为顶点的三角形加入到三角形列表L中。 步骤11 分别更新d1,d2,d4的边表，删除所有边使用次数flag=2的点。返回步骤3，直至查找完n个点后输出结果，终止。

4算法实现与分析

本人使用VB语言对改进前算法和改进后算法进行实现。实现结果如图4-1和图4-2所示。