ドロネー三角形分割

Question

は、私が凸包を終えたとpoints.Iの最も近いペアは、ドロネー三角形分割の格差を書いて、code.Butを征服する必要があります私は、誰でもDTのために私のシリアルコードを提供するか、または少なくとも私は凸包からドロネー三角形分割を生成することができる方法を知らせることができれば凸包はcalculated.Soをすることができた場合にどこかにそのドロネー三角形分割を容易に実現することができます読んで多くのtime.Iを持っていけません、私はコードを書くことができ、できるだけ早くそれを並列化することができます。

Answer 1

凸包を計算することができれば、delaunay三角形分割は簡単に実装できます。

これは真実であるが、正確な文は、次元凸包実装が利用可能である場合2Dドロネー三角形を容易に構築することができることです。 2Dの船体を知ることは、あなたにDTのいくつかのエッジを（各船体のエッジはDTのエッジである）を与えるほか、ドロネー三角形分割（DT）を構築してあまり役立ちません。

3D船体を実装していないと仮定すると（それはかなり難しい）、のDelaunay三角測量を個別に攻撃する必要があります。

Answer 2

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