Ruppert's Algorithm 曹玮，金逸飞，沈彤
算法简介
Delauney三角化实现了质量很高的点集三角化。
但是，特定的输入会造成三角化的结果包含很多形状较细的三角形，如左图。
在这种情况下，一般采用加点的方法，使得三角化结果较为均匀，如右图。
这样的结果一般用于有限元分析、mesh生成等领域。
Ruppert的算法是这方面的奠基性工作。
它通过最少的加点，达到所有三角形的最小角度不小于设定的阈值的目的。
它通过最少的加点，达到所有三角形的最小角度不小于设定的阈值的目的。
视频展示
程序基本流程：
- 点击“Load from file”按钮，选择一个poly文件
- 点击“Step1”按钮，进行初始Delauney三角化
- 点击“Step2”按钮，通过加入线段中点，消除一些过细的三角形。可以点击“Step2 Single”按钮观看单步动画
- 点击“Step3”按钮，去除多余三角形
- 点击“Step4”按钮，通过加入三角形外心或线段中点，消除一些过细的三角形。可以点击“Step4 Single”按钮观看单步动画
- 算法结束
自定义模型：
- 点击“Create new model”按钮
- 绘制一系列点，组成模型的外边界
- 绘制一系列点，组成模型内部的孔洞边界
- 将“Mode”设置为“Point”
- 在每一个孔洞之内点一个点
- 点击“Save to file”按钮，进行保存
算法介绍
算法输入
- 外边界，以边集合的形式给出。必须是多边形
- 内部孔洞的边界，以边集合的形式给出。可以是多边形，也可以只有一条线段
注意Ruppert算法有一个限制：外边界不能有小于60度的尖角出现，否则算法可能会一直加点，无法正常结束。
算法流程
- 以输入图的顶点为输入，计算Delaunay 三角剖分。将剖分结果保存成 T
- 统计所有 Encroach 的边，即所有没有用到的输入边和直径圆中包含其他顶点的边。
- 给Encroach的边加中点，使得新的三角剖分用到了所有的输入边。
- 删除所有边界外的三角形
- 迭代处理所有skinny 三角形（即，最小角小于阈值的三角形）。给这些三角形加外心。如果外心没有引起Encroach，则加入；若引起Encroach， 跳转到第二步处理Encroach。
- 迭代结束，输出Ruppert算法的剖分结果
算法输出
加点后的三角化，满足所有三角形的最小角度不小于设定的阈值运行说明
- 下载打包好的可执行文件
- 安装压缩包中的vcredist_x86.exe文件
- 运行Demo.exe
这里仅对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