当前位置:   article > 正文

二维Delaunay(德洛内)三角网剖分的matlab实现

delaunay

二维Delaunay(德洛内)三角网的matlab实现

1.Delaunay三角网的概述

德洛内(Delaunay)三角网的定义: 它是一系列相连的但不重叠的三角形的集合, 而且这些三角形的外接圆不包含这个面域的其他任何点。它具有两个特征:

(1) 每个德洛内(Delaunay) 三角形的外接圆不包含面内的其他任何点, 称之为德洛内(Delaunay) 三角网的空外接圆性质, 这个特征已经作为创建德洛内(Delaunay) 三角网的一项判别标准;

(2) 它的另一个性质最大最小角性质: 每两个相邻的三角形构成的凸四边形的对角线,在相互交换后,六个内角的最小角不再增大。

Delaunay 三角网的优点是结构良好, 数据结构简单, 数据冗余度小, 存储效率高, 与不规则的地面特征和谐一致,可以表示线性特征和迭加任意形状的区域边界, 易于更新,可适应各种分布密度的数据等; 它的局限性是, 算法实现比较复杂和困难, 但现在已经有了较多成熟的实现算法。

以上直接复制百度百科的。
下面是一个自己做的Delaunay三角网的划分的演示实例

一个演示实例
其中Voronoi图(泰森多边形)的画法:https://blog.csdn.net/weixin_42943114/article/details/82319332
彩色Voronoi图的画法:https://blog.csdn.net/weixin_42943114/article/details/82461228

本文的算法和思路主要采用
三角剖分算法(delaunay) http://www.cnblogs.com/zhiyishou/p/4430017.html

下面这几篇文章也给我了很大的启发
1.delaunay三角剖分的几种算法综述 http://www.doc88.com/p-468115276920.html
2.Delaunay三角剖分 https://blog.csdn.net/xwebsite/article/details/5778347
3.Delaunay三角剖分及matlab实例 https://blog.csdn.net/piaoxuezhong/article/details/68065170
4.从Delaunay三角化到网格质量 https://blog.csdn.net/xs1997/article/details/76945193

2.Delaunay三角网的算法

本文的算法采用的是改进型的驻点插入算法,也就是Bowyer-Watson算法。由于前面具体的算法概述和参考的文章大致相同,所以就不再多说了(其实就是懒得复制粘贴了)。
这个算法采用的比较广泛,效果比较好,而且在原网格中插入新点会更方便,但是缺点是不太好理解。

主要思路是:
1。先构建一个超级三角形,把所有点包围起来
2。之后依次一个一个插入点。(a)在网格中插入新点 (b)相关三角形画外接圆,记录下所有外接圆包含新点的三角形 ©删除影响三角形的公共边 (d)重新规划新边
3。记录三角形至网格中
4。重复步2,直至所有点插入
5。删除超级三角形以及和其相关的三角形。

图

算法的伪代码如下:

input: 顶点列表(vertices)                       //vertices为外部生成的随机或乱序顶点列表
output:已确定的三角形列表(triangles)
    初始化顶点列表
    创建索引列表(indices = new Array(vertices.length))    //indices数组中的值为0,1,2,3,......,vertices.length-1
    基于vertices中的顶点x坐标对indices进行sort           //sort后的indices值顺序为顶点坐标x从小到大排序(也可对y坐标,本例中针对x坐标)
    确定超级三角形
    将超级三角形保存至未确定三角形列表(temp triangles)
    将超级三角形push到triangles列表
    遍历基于indices顺序的vertices中每一个点            //基于indices后,则顶点则是由x从小到大出现
      初始化边缓存数组(edge buffer)
      遍历temp triangles中的每一个三角形
        计算该三角形的圆心和半径
        如果该点在外接圆的右侧
          则该三角形为Delaunay三角形,保存到triangles
          并在temp里去除掉
          跳过
        如果该点在外接圆外(即也不是外接圆右侧)
          则该三角形为不确定                      //后面会在问题中讨论
          跳过
        如果该点在外接圆内
          则该三角形不为Delaunay三角形
          将三边保存至edge buffer
          在temp中去除掉该三角形
      对edge buffer进行去重
      将edge buffer中的边与当前的点进行组合成若干三角形并保存至temp triangles中
    将triangles与temp triangles进行合并
    除去与超级三角形有关的三角形
end
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

这篇文章(三角剖分算法(delaunay) http://www.cnblogs.com/zhiyishou/p/4430017.html)有一个用三个点的实例来演示这个程序运行的结果,如果可以的话,也推荐用三个点或4个点来检测一下自己程序运行的效果。

3.Delaunay三角剖分的matlab实现

下面是matlab实现的源代码,之后会解释一下实现的思路

clear
N=1000;
%点随机
xdot=rand(N,2);
%点按圆形随机
%r=rand(N,1).^0.3;
%theta=rand(N,1)*2*pi;
%xdot=[r.*cos(theta),r.*sin(theta)];
%点按圆形规则
% r=0:0.001:1;
% r=r.^0.8;
% theta=0:0.1:1000*0.1;
% theta&
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/正经夜光杯/article/detail/876756
推荐阅读
相关标签
  

闽ICP备14008679号