凸包の作成:Quickhull 法


点群(点データの集合体)を凹みのないように覆った図形を凸包と呼びます。凸包作成アルゴリズムはいくつかありますが、Molcer Plus では高速な Quickhull 法を採用しています。

凸包
凸包

Quickhull 法

  1. 座標の最大・最小点を求める
    Quickhull法・最大最小点
  2. 1の2点で領域分割
    Quick Quickhull法・領域分割
  3. 直線の再遠点を求める
    Quickhull法・再遠点
  4. エッジ作成
    Quickhull法・エッジ作成
  5. 内側の点とエッジを無視する
    Quickhull法・内側無視
  6. 3に戻る(各エッジの外側について再帰的に行う。外側の点が無くなったら終了)
    Quickhull法・再帰処理

上記は二次元平面における凸包です。これを三次元空間に数学的に拡張して3Dデータの凸包を作成します。

三次元の場合は四面体を形成してから各面を処理していきます。また、凹みや谷折れ構造の修正が必要になってきます。