一、三角剖分Delaunay算法簡(jiǎn)介
點(diǎn)集的三角剖分（Triangulation），對(duì)數(shù)值分析（比如有限元分析）以及圖形學(xué)來(lái)說(shuō)，都是極為重要的一項(xiàng)預(yù)處理技術(shù)。尤其是Delaunay三角剖分，由于其獨(dú)特性，關(guān)于點(diǎn)集的很多種幾何圖都和Delaunay三角剖分相關(guān)，如Voronoi圖，EMST樹，Gabriel圖等。Delaunay三角剖分有最大化最小角，“最接近于規(guī)則化的“的三角網(wǎng)和唯一性（任意四點(diǎn)不能共圓）兩個(gè)特點(diǎn)。
?EMST(Euclidean minimum spanning tree)
Delaunay 三角剖分廣泛應(yīng)用于許多不同應(yīng)用程序中的科學(xué)計(jì)算。雖然有大量的計(jì)算三角剖分的算法，但 Delaunay 三角剖分以其實(shí)用的幾何屬性廣受歡迎。
?Gabriel Graph
基本屬性是 Delaunay 規(guī)則。如果是二維三角剖分，通常將其稱為空外接圓規(guī)則。對(duì)于一組二維點(diǎn)而言，這些點(diǎn)的 Delaunay 三角剖分可確保與每個(gè)三角形相關(guān)的外接圓的內(nèi)部都不包含其他點(diǎn)。這種三角剖分便是 Delaunay 三角剖分。
Delaunay 三角剖分堪稱“外形整齊”，原因在于為滿足空外接圓屬性，優(yōu)先選擇帶有較大內(nèi)角的三角形，而不是帶有較小內(nèi)角的三角形。非 Delaunay 三角剖分中的三角形在頂點(diǎn) V2 和 V4 處呈銳角。如果將 {V2, V4} 邊替換為連接 V1 和 V3 的邊，會(huì)實(shí)現(xiàn)最小角的最大化并且使得該三角剖分變?yōu)?Delaunay 三角剖分。另外，Delaunay 三角剖分將最近鄰點(diǎn)的點(diǎn)連接在一起。這兩個(gè)特征（外形整齊和最近鄰點(diǎn)關(guān)系）在實(shí)踐中具有重要的作用，有助于促進(jìn)在散點(diǎn)數(shù)據(jù)插值中使用 Delaunay 三角剖分。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-839062.html
雖然 Delaunay 屬性定義明確，但存在退化點(diǎn)集時(shí)三角剖分的拓?fù)洳⒉晃ㄒ弧Ｔ诙S中，4 個(gè)或更多特征點(diǎn)位于同一圓中時(shí)會(huì)引發(fā)退化。例如，正方形的頂點(diǎn)不具有唯一的 Delaunay 三角剖分。
?文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-839062.html
二、三角剖分Delaunay算法的源代碼
namespace Legalsoft.Truffer.Algorithm
{
public struct Vertex
{
public int x;
public int y;
public int z;
}
public struct Triangle
{
public int vv0;
public int vv1;
public int vv2;
}
public class Delaunay
{
public const int MaxVertices = 500;
public const int MaxTriangles = 1000;到了這里，關(guān)于C#，計(jì)算幾何，隨機(jī)點(diǎn)集之三角剖分的德勞內(nèi)（Delaunay）算法的源代碼的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
