成果物
Convex hullの投影
www.youtube.com
この動画を見ればわかるとうり、Convex hullを平面に投影すると見事にDelaunay Triangulationになることがわかります。初めて知ったときは本当に驚きました。また、Convex hullの計算時に隣接する面のデータを含んでいるので簡単にVoronoi図も作成できます。
2D/3DのDelaunay Triangulation
www.youtube.com
Quickhullという方法を使うと、Convex hullを高次元に拡張することができます。
nekodigi.hatenablog.com
3DのDelaunay Triangulationは4DのConvex hullを使うことで簡単に求めることができます。
仕組み
全ての頂点を含むConvex hullを作るには頂点をおわん型に配置すればよいので、原点からの二乗距離の分だけ上に移動させれば実現することができます。
また、Delaunay TriangulationはConvex hullの下面のみなので法線の向きを調べることで、有効な面を調べています。
コード
github.com
今回は、こちらのサイトに本当にお世話になっています。
github.com
