ドロネー三角形分割
ソースコード
nachia/geometry/delaunay-triangulation.hpp
主な機能
ドロネー三角形分割で得られる辺を列挙する。
構造体テンプレート DelaunayTriangulation
テンプレート引数
template<class Int = long long, class Int2 = long long>
class DelaunayTriangulation;
入力に使用する整数型 Int と、内部で使用する大きい整数型 Int2 を設定できる。
コンストラクタ
DelaunayTriangulation();
DelaunayTriangulation(std::vector<VecI2<Int,Int2>> x_points);
- 要素数 $n$ : $0 \leq n \leq 10^8$
- 座標が同じ $2$ 点はない
- $2$ 座標の差に任意の符号を付けた値が
Int型に収まる - $2$ 座標の差の絶対値の最大を $d$ とするとき、
Int2型は $\pm 12d^4$ の範囲を扱える。 - $O(n\log n)$ 時間
引数を与えない場合は $0$ 頂点について計算を行う。
getEdges
std::vector<std::pair<int, int>> getEdges();
計算された辺をすべて得る。 $(a,b)$ 間に辺がある場合、 $(a,b)$ または $(b,a)$ のどちらか一方のみが出力に含まれる。