delaunay三角网的特点,delaunay三角化

　　1.概述2。图解说明1。插入第一个点2。插入第二点3。插入第三点4。插入第四点5。插入第五条边6。去除超级三角形3中有极值的边。房产：4。代码：1。伪代码：2。执行：3。C#实现：参考：

　　一.概述

　　我还有一些细节需要整理，希望大家多多交流。

　　要了解什么是Delaunay三角，可以看看其他博客，或者看看纸兽大佬们做的演示网站。写的很清楚，下面有图(其实这个方法的点可以是任意维的点，这里只是二维的例子):

　　下面是实现的方法。

　　方法判断一个三角形是否是Delaunay三角形非常简单。这个三角形是一个外接圆，外接圆内或外接圆上没有其他点。

　　有许多方法可以实现它：

　　鲍耶-沃森算法

　　第二，图形解释主要靠维基百科。我有些地方不太懂维基的彩图，所以下面所有的图都不是维基的原图。为了方便起见，我对它们进行了修改。可能是我理解的不对吧。如果你忘记了，请改正它们。

　　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的外接圆，后面还要看代码，这里就清楚了。

　　根据伪代码，删除不满足判断条件的三角形的共享边。

　　对于三角形中的每条边，如果该边不被坏三角形中的任何其他三角形共享，则将边添加到多边形，S1P2 S 1 P 2仍被删除，绿线变为红线。

　　4.插入第四点。

　　这一次，真好。红线内的三角形都满足判定条件。红线直接变成绿线。

　　5.插入第五条边

　　方法同上，去掉两个黄色外接圆，去掉P3S2 P 3 S 2，绿线变成红线。

　　6.去掉超级三角形中有极值的边，最后蓝色的边就是我们找到的。

　　自然：我不喜欢细三角形。

　　所谓薄，就是钝角很大的钝角三角形。

　　四。代码：1。伪代码：

　　首先，下面说的遍历三角形不包括超三角形，坏三角形是不满足文章开头判断条件的三角形。Poly是一个polygan，是我们删除了一些边之后的中间过程的图。好的一面是我们想留下的一面。

　　三角剖分是我们目前有效的图。

　　主要有两个for循环，第二个for循环是从左边完成后去掉多余的边。它对应于图6。

　　先看主for循环遍历点集中的所有点：

　　遍历所有三角形。如果不满足判断条件，就加到坏三角形上，遍历所有坏三角形的所有边。找到好的一面。遍历所有坏三角形。删除坏边。穿过好的边缘。添加到有效图形。

　　2.c .实现：实现库

　　Python opencv实现

　　基本上我都是在网上阅读学习opencv。我在这里只是记录自己的过程。

　　一个好的链接和三个可以运行的代码，点击这里3。C#实现：https://blog.csdn.net/k346k346/article/details/52244123.

　　参考：维基鲍耶沃森算法3359 www . cn blogs . com/zhiyishou/p/4430017 . html 3359 blog . csdn . net/new thinker _ Wei/article/details/45598769https://blog . csdn . net/k346k 339