Delaunay 三角剖分生成器

Delaunay 三角剖分生成器可將任何 2D 點集轉換為最大化最小內角的唯一三角剖分 — 這是地形建模、有限元素網格劃分、最近鄰插值和計算幾何課堂的金科玉律。貼上座標（或選擇一個快速啟動樣式），該工具就會在伺服器端執行 Bowyer-Watson 演算法，根據質量對每個三角形進行著色，並根據需求顯示空外接圓性質、凸包和 Voronoi 對偶。

如何讀取生成的網格

是什麼讓這個 Delaunay 三角剖分生成器與眾不同

什麼是 Delaunay 三角剖分？

給定一組 2D 點，通常有很多方法可以將它們連接成三角剖分（由三角形對其凸包進行完整鋪磚，沒有重疊或間隙）。以俄羅斯數學家 Boris Delaunay (1934) 命名的 Delaunay 三角剖分是滿足空外接圓性質的三角剖分：對於網格中的每個三角形，通過其三個頂點的圓不包含其他輸入點。這單一性質帶來了一個顯著的結果：在同一點集的所有三角剖分中，Delaunay 三角剖分使最小內角最大化。簡單來說，它能產生盡可能最「飽滿」且「平衡」的三角形。

Bowyer-Watson 演算法如何運作

1. 用一個非常大的超三角形包圍所有輸入點。
2. 一次插入一個輸入點。對於每個新點，找出外接圓包含該新點的所有現有三角形 — 這些是「壞」三角形。
3. 移除壞三角形。它們留下的洞具有多邊形邊界。
4. 將新點連接到該邊界的每條邊，形成新的三角形。
5. 插入所有點後，移除任何仍與超三角形頂點接觸的三角形。剩下的是原始點集的 Delaunay 三角剖分。

Delaunay 三角剖分應用於何處

• 地形建模 (GIS)：高程樣本（通常是不規則間隔的，如地形站）被連接成不規則三角網 (TIN)，用於高程查詢、陰影和 3D 視覺化。
• 有限元素分析：形狀良好的 Delaunay 三角形可為力學、熱傳導和電磁學中的偏微分方程提供穩定的數值解。
• 電腦圖形學：用於渲染、角色骨架綁定和程序化地形的網格生成 — Delaunay 的「無狹長三角形」保證可避免紋理拉伸偽影。
• 自然鄰點插值：透過 Voronoi 對偶計算每個查詢點的自然鄰點，從分散的樣本中重建平滑表面。
• 計算幾何課程：一種與凸包、Voronoi 圖、點定位和分治法有深厚聯繫的經典演算法。
• 3D 列印切片機和 CNC 工具路徑：2D Delaunay（及其 3D 堂兄 Delaunay 四面體剖分）是許多切片和填充策略的基礎。

Delaunay 與 Voronoi：一體兩面

Voronoi 圖將平面分割為每個輸入點一個單元格，其中每個單元格包含比任何其他點都更接近其點的所有內容。連接單元格共享邊界的點，您將精確地得到 Delaunay 三角剖分。相反地，相鄰 Delaunay 三角形的外接圓心由線段連接，形成了 Voronoi 邊。在此工具上切換「Voronoi 對偶」以查看疊加在同一圖表上的橘色虛線 — 每條 Delaunay 邊都與一條 Voronoi 邊成直角相交。

質量、狹長三角形與網格細化

Delaunay 最大化了全域最小內角，但它無法修正根本上糟糕的點分佈。如果您的輸入點接近共線、聚集或留下很大的空白區域，某些三角形仍然會是狹長的（最小內角低於 20°）。修正方法是插入 Steiner 點：諸如 Ruppert 演算法和 Chew 第二演算法之類的演算法，在狹長三角形的外接圓心處迭代加入新點，每次都重新進行三角剖分，直到每個三角形都達到目標質量邊界。此生成器向您顯示哪些三角形是狹長的，以便您在想要更細緻的網格時知道在何處加入 Steiner 點。

實際範例

點擊「圓形 + 中心」預設。該工具在圓形周圍放置 18 個點，並在中心放置 1 個點，然後對它們進行三角剖分。結果是一個由 18 個等腰三角形在中心相交的完美扇形 — 每個三角形在邊緣處的角度為 10°，在中心處的角度為 80°–80°。最差最小內角為 10°，所有三角形都被標記為狹長，且直方圖顯示所有內容都在 0°–10° 區間內。這個範例是一個很好的教學案例：當輸入強迫時，即使是 Delaunay 最優三角剖分也可能包含狹長三角形。現在點擊「隨機雲」 — 相同的演算法會產生形狀良好的三角形，因為點分佈均勻，且直方圖向右移動。

常見誤解

• 「Delaunay 三角剖分是唯一的」：通常是的，但如果四個輸入點共圓（全部位於同一個圓上），則該組有兩個有效的 Delaunay 三角剖分。生成器會始終如一地選擇其中一個。
• 「更多點總是意味著更好的質量」：加入放置不當的點可能會引入新的狹長三角形。Steiner 點演算法會小心地將新點放置在 — 外接圓心 — 處，因此質量保證會得到改善。
• 「Delaunay 與凸包相同」：不。凸包是外邊界；Delaunay 三角剖分用三角形填充內部。
• 「所有三角剖分看起來都差不多」：差異是巨大的。從 Delaunay 邊進行「翻轉」可以將 25° 的三角形變成 5° 的三角形。該工具的質量熱圖使這種差異變得顯而易見。

常見問題