computational-geometry - 凸包からのドロネー三角形分割

Question

計算幾何学にいくつかのコードを記述し、openMPを使用してそれらを並列化する必要があります。これまでに、凸包と最も近い点のペアを完成させました。ドロネー三角形分割分割統治コードを記述する必要があります。しかし、時間があまりありません。凸包を計算できれば、どこかでドロネー三角形分割を簡単に実装できるので、誰かがDTのシリアルコードを提供してくれるか、少なくとも凸包からドロネー三角形分割を生成する方法を教えてください。コードを記述して並列化できます。できるだけ早くそれ。

Answer 1

凸包を計算できれば、ドロネー三角形分割を簡単に実装できることをどこかで読みました。

これは真実ですが、正確な説明は、 3D凸包の実装が利用可能であれば、 2Dドロネー三角形分割を簡単に構築できるということです。2D船体を知ることは、DTのいくつかのエッジを提供する以外に、ドロネー三角形分割（DT）の構築にはあまり役立ちません（各船体エッジはDTのエッジです）。

3Dハルを実装していないと仮定すると（これは非常に注意が必要です）、Delaunay三角形分割を個別に攻撃する必要があります。

Answer 2

QHullは、多くの人が使用するほぼ標準のライブラリです。http ://www.qhull.org/html/qhull.htm これを本当に再実装したい場合は、おそらくリファレンス実装として使用できます。