algorithm - メッシュを四面体に分割しますか？

Question

閉じた多面体を作成するために、面と線で接続された任意の点のセットがあるとします。そのようなメッシュを四面体のグループに分割できるアルゴリズムはありますか？

Answer 1

の点の制約付きドロネー三角形分割（つまり、四面体化）を構築することを検討できますR^3。ここで、制約はエッジと三角形の面のリストです。

ただし、2を超える次元では、このような制約された三角形分割を直接形成できるとは限らないことに注意してください。良い例は、Schonhardt多面体です。このような多面体を処理するには、追加の頂点を導入して制約を「分割」する必要があります。私が理解しているように、これを行うための「最良の」方法を決定することはまだオープンな研究領域ですが、さまざまなヒューリスティックなアプローチが提案されています。

この分野でのJonathanShewchukの研究/ソフトウェア、特に彼の論文に興味があるかもしれません。

• 制約付きドロネー四面体化とおそらく良好な境界回復
• フリップによる制約付きドロネーおよび制約付き通常三角形分割の更新と構築

高次元の制約付き三角形分割の問題のいくつかに対処します。

また、私はあなたの問題が自明ではないと仮定しました-非凸多面体を定義する一連の制約があります。凸制約の場合、これらは、制約のないドロネー三角形分割を計算するだけで直接回復する必要があります。これは、任意の次元で存在することが保証されています。