一，概述
本人还有一些细节没理清，所以希望大家多多交流
二，图形化解释
主要看的维基百科，对于wiki的图示有些地方我不是太看懂他的颜色图示，所以以下所有的图都不是wiki的原图，为了方便说明我对其做了修改，也许我理解的不对，忘请纠正
1. 超级三角形插入第一个点
我们一共有五个点做Delaunay三角化,首先需要注意一点，以下图中的正方形方框，假设就是图片大小，所有的点都必须在这个方框内，而超级三角形只是为了算法的实现，有外接矩形所构造的一个虚拟的三角形
2. 插入第二个点
* 给图中所有红边三角形(除去超级三角形，下文同样), 做外接圆
* 新插入的点P2在 S1S2P1 S 1 S 2 P 1 ， S0P2S2 S 0 P 2 S 2 的外接圆内，所以删除线 S2P1 S 2 P 1 ，
* 并同时把绿色线变成红色线(绿色线其实在判断完新插入点的条件后，要连接的线，为下一个点的插入做准备)，变成下图：
3. 插入第三个点
对所有红线构成的三角形做外接圆，判断点P3是不是在外接圆内。显然 S1P2S2 S 1 P 2 S 2 外接圆不符合条件，所以要删除这个三角形，问题是删除哪条边。我觉得有两种解释:
* 超级三角形的边是不会删除的，而 S1P2S2 S 1 P 2 S 2 外接圆符合判定条件，所以 S2P2 S 2 P 2 不删除
* 三角形 S1P1P2 S 1 P 1 P 2 的外接圆不符合判定条件，与 S1P2S2 S 1 P 2 S 2 外接圆公共边是 S1P2 S 1 P 2 ，所以删除 S1P2 S 1 P 2
个人倾向于第一种，因为wiki给的图没有 S1P1P2 S 1 P 1 P 2 的外接圆，后期还要看一下代码，这里才清楚
根据伪代码，是删除不符合判定条件的三角形共享的边
for each edge in triangle do if edge is not shared by any other triangles in badTriangles add edge to polygon依旧删除 S1P2 S 1 P 2 ，绿线变成红线
4. 插入第四个点
5. 插入第五个边
方法同上,两个黄色的外接圆,去掉 P3S2 P 3 S 2 ，绿线变红线
6. 在超级三角形中移除具有极值的边
最后蓝色的边就是我们所求得
三，性质：
- 不喜欢瘦的三角形
所谓的瘦，就是一个钝角很大的钝角三角形
四，代码：
1. 伪代码：
首先说明一下，下面说的遍历三角形不包括超级三角形，坏三角形就是不符合文章开头判定条件的三角形.。polygan是多边形，是我们删掉一些边后中间过程的图形。好边就是我们要留下的边。
triangulation就是我们现在的有效图形的。
两个主要的for循环，第二个for循环就是从左完成以后去掉多余的边。就是对应图示6
主要看第一个for循环遍历点集中的所有的点:
- 遍历所有三角形。不符合判定条件的，添加到坏三角形
- 遍历所有坏三角形的所有边。找出好边。
- 遍历所有坏三角形。删掉坏边。
- 遍历好边。加到有效图形当中
2. C++实现：
- 实现的库
- C++
- Python
- opencv实现
网上的基本都是看着
<学习opencv>
这本书写的，我这里只是记录一下自己的过程。
一个不错的链接而且有三个能跑的代码，点这里
3. C#实现：
https://blog.csdn.net/k346k346/article/details/
参考：
- wiki Bowyer–Watson algorithm
- https://www.cnblogs.com/zhiyishou/p/4430017.html
- https://blog.csdn.net/NewThinker_wei/article/details/
- https://blog.csdn.net/k346k346/article/details/
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/224149.html原文链接：https://javaforall.net
