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 ) O(n^3) O(n3)
- 可以生成帶孔多邊形的算法
- 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 ) O(n\log n) O(nlogn)
- 普通的Delaunay三角剖分算法不能對帶孔多邊形進行三角剖分
約束Delaunay三角剖分算法 (CDT) O ( n log ? n + m log ? n ) O(n\log n+m\log n) O(nlogn+mlogn)
- 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