C-11 三角剖分算法

• 三角剖分就是將輸入的多邊形，分割成一系列互不重疊的三角形，其重要性就在這不多贅述。
• 這個是一個別人總結的鏈接：http://vterrain.org/Implementation/Libs/triangulate.html
  

圖片鏈接：http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Thierry/thierry507webprj/complexity.htm

耳切割算法 （eat-cut） $$O(n^3)$$

• 可以生成帶孔多邊形的算法
• GitHub地址： https://github.com/mapbox/earcut.hpp
• 這是生成凹多邊形的算法，簡單來說，凹下去的那一個頂點就是耳朵，先生成多邊形的凸包，然后找到該多邊形上凹下去的頂點，把那部分給“切”掉，這就是而且個算法

#include <earcut.hpp>// The number type to use for tessellation
using Coord = double;// The index type. Defaults to uint32_t, but you can also pass uint16_t if you know that your
// data won't have more than 65536 vertices.
using N = uint32_t;// 創建多邊形
using Point = std::array<Coord, 2>;
std::vector<std::vector<Point>> polygon;//放入輪廓線
polygon.push_back({{100, 0}, {100, 100}, {0, 100}, {0, 0}});
//放入洞，除了第一條線是輪廓線之外，從第二條線開始就是洞線了
polygon.push_back({{75, 25}, {75, 75}, {25, 75}, {25, 25}});//返回索引值
std::vector<N> indices = mapbox::earcut<N>(polygon);
//讀取索引值就是離散化完成的三角形了

Delaunay三角剖分算法 $$O(n\log n)$$

• 普通的Delaunay三角剖分算法不能對帶孔多邊形進行三角剖分

約束Delaunay三角剖分算法 （CDT） $$O(n\log n+m\log n)$$

• CGAL幾何庫采用的就是這種三角剖分算法，因此無論是時間上還是穩定性上這種算法都是值得信賴的
• 時間復雜度中的m是指輪廓邊和孔洞邊的數量
• GitHub地址： https://github.com/artem-ogre/CDT
• 算法步驟
  • 和Delaunay一樣 先生成super triangle
  • 然后剔除super triangle帶來的邊
  • 剔除外輪廓邊之外的邊
  • 剔除孔洞之中的邊

單調多邊形三角化

• 這個我也沒大看懂，也沒有自己代碼實現過，所以不敢妄言
• 簡單的說一說就是把一個多邊形分成若干個單調多邊形(Monotone Polygon)。然后將單調多邊形進行三角剖分
• 單調多邊形是指一個有兩條鏈子組成的多邊形，然后兩條鏈子上的頂點的縱坐標是遞增的或者橫坐標是遞增的。比如下面是一個y單調多邊形，就是縱坐標遞增。坐標相等也算遞增，比如長方形也是單調多邊形。
• 這個思想就很有意思，就如同紅黑樹一樣，介于平衡二叉樹和普通二叉樹之間。單調多邊形就介于凸多邊形和凹多邊形之間。凸多邊形必然是一個單調多邊形，而凹多邊形就不一定了。
• 把一個多邊形分成單調多邊形的過程(line sweep)的時間復雜度是O(nlogn)，而對一個單調多邊形進行三角劃分的時間復雜度是O(n);
• https://www.cnblogs.com/dogstar/archive/2011/04/07/2008726.html 這個大佬的博客有多邊形單調劃分相關步驟的說明。也有單調多邊形三角化的說明，可以看看
• 在計算幾何算法與應用這本書里面，也有算法的詳細說明
• 《計算幾何算法與應用(第三版)》 鏈接：https://pan.baidu.com/s/1exLpWuD5cBcZGasWH8Y3_w 提取碼：6666

其他的剖分算法

• https://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml
• http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html

參考資料

• 一個多邊形三角剖分匯總網站 http://vterrain.org/Implementation/Libs/triangulate.html
• 《J. O’Rourke, Computational in C, 2nd Edition》鏈接：https://pan.baidu.com/s/1E4tYKPJ2miU9OXRpw0tWng 提取碼：6666