Ruppert's Algorithm    曹玮,金逸飞,沈彤

算法简介


Delauney三角化实现了质量很高的点集三角化。
但是,特定的输入会造成三角化的结果包含很多形状较细的三角形,如左图。
在这种情况下,一般采用加点的方法,使得三角化结果较为均匀,如右图。
这样的结果一般用于有限元分析、mesh生成等领域。
Ruppert的算法是这方面的奠基性工作。
它通过最少的加点,达到所有三角形的最小角度不小于设定的阈值的目的。

视频展示


程序基本流程:

自定义模型:

算法介绍


算法输入

  1. 外边界,以边集合的形式给出。必须是多边形
  2. 内部孔洞的边界,以边集合的形式给出。可以是多边形,也可以只有一条线段
注意Ruppert算法有一个限制:外边界不能有小于60度的尖角出现,否则算法可能会一直加点,无法正常结束。

算法流程

  1. 以输入图的顶点为输入,计算Delaunay 三角剖分。将剖分结果保存成 T
  2. 统计所有 Encroach 的边,即所有没有用到的输入边和直径圆中包含其他顶点的边。
  3. 给Encroach的边加中点,使得新的三角剖分用到了所有的输入边。
  4. 删除所有边界外的三角形
  5. 迭代处理所有skinny 三角形(即,最小角小于阈值的三角形)。给这些三角形加外心。如果外心没有引起Encroach,则加入;若引起Encroach, 跳转到第二步处理Encroach。
  6. 迭代结束,输出Ruppert算法的剖分结果

算法输出

加点后的三角化,满足所有三角形的最小角度不小于设定的阈值

运行说明


这里仅对Ubuntu 14.04提供支持,其他发行版类似
  • 安装matplotlib, opengl和numpy:sudo apt-get install python-matplotlib python-numpy python-opengl
  • 安装python扩展工具:sudo apt-get install python-setuptools
  • 安装python扩展triangle:sudo easy_install install triangle
  • 编译安装PyQt5:下载sip和PyQt5,解压后运行python configure.py && make && sudo make install
  • 执行Demo.py:python Demo.py

源代码


实验报告


相关链接