寻找点集中ｙ轴值最小的Ｐ点 将Ｐ点与其他各个顶点链接起来。计算线段和水平线的夹角
•
• •
按照夹角大小对点排序，若夹角相同，按照距离排序
依次链接所有顶点，得到多边形 根据“凸多边形的各顶点必在该多边形的任意一条边的同侧”定理，删除非凸壳 顶点，得到边界。
凸壳生成算法
分割采样点
凸壳生成算法
P2
1、构造子网边界 2、三角化子网
P4 P3
P5 P1 P0
分割合并算法
P3 P2
1、构造子网边界 2、三角化子网 3、类似构造另外一个子集
P5
P4 P3 P4
P2
4、底线和顶线的查找
P0
P1 P5
P1
P0
Xmax Xmin
分割合并算法
P3 P2
1、构造子网边界 2、三角化子网 3、类似构造另外一个子集
P5
P4 P3 P4
P2
4、底线和顶线的查找 5、合并三角形
分割合并算法
分割合并算法步骤
S1 将数据集以横坐标为主、纵坐标为辅按升序排序。 S2 如数据集中点数大于阀值，则继续将数据集化为点个数近似相等 的两个子集，并 对每个子集做如下工作： ① 获取每子集的凸壳； ② 以凸壳为数据边界进行三角化，并用LOP优化成D三角网； ③ 找出连接左右子集两个凸壳的底线和顶线； ④ 由底线到顶线合并两个三角网。 S3 如数据集中点数不大于阀值，则直接输出三角剖分结果。
分割合并算法要点：
1、数据点集采用递归分割快速排序法；
2、子集凸壳的生成可采用格雷厄姆算法； 3、子集三角化可采用任意方法，3或4个点可直接三角剖分；
4、子网合并则需先找出左右子集凸壳的底线和顶线;
5、逐步合并三角剖分得到最终D三角网（三角网的局部优化）。
凸壳生成算法流程
•
• •
将数据集按照以横轴为主，纵轴为辅升序排序
P0
P1 P5
P3 P2
1、构造子网边界 2、三角化子网 3、类似构造另外一个子集
P5
P4 P3 P4
P2
4、底线和顶线的查找 5、合并三角形 6、LOP法则局部优化
P0
P1 P5
P1
P0