Delaunay三角化实现原理

2023-11-16

一，概述
二，图形化解释
三，性质：
四，代码：
参考：

一，概述

本人还有一些细节没理清，所以希望大家多多交流

了解定义什么是Delaunay三角大家可以看其他博客，或者看纸异兽大佬做的演示网站写的很清楚了，这里一张图带过(实际上这个方法的点可以是任意维度的点，这里只是以二维举一个例子)：
这里写图片描述

这里主要说一下怎么实现的
判断方法三角形是不是Delaunay三角形很简单，这个三角形做外接圆，外接圆内或者圆上没有其他点
实现方法很多：
这里写图片描述
这里说的Bowyer–Watson algorithm

二，图形化解释

主要看的维基百科，对于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. 插入第四个点

这里写图片描述

这次很nice，红线的三角形都满足判定条件。直接红线变成绿线
这里写图片描述

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/52244123

参考：

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)