algorithm - 3 次元曲面の凸包アルゴリズム z = f(x, y)

Question

トリプル (x_i、y_i、z_i) のセットとして与えられた 3D サーフェスがあります。ここで、x_i と y_i はおおよそグリッド上にあり、各 (x_i、y_i) には関連付けられた単一の z_i 値があります。一般的なグリッドは 20x20 です

与えられた許容範囲内で、サーフェスの凸包に属するポイントを見つける必要があります。計算を実行するための効率的なアルゴリズムを探しています (私の顧客は、400 ポイントのデータセットで ~10 秒かかる O(n³) バージョンを提供しています...)

score 5 · Accepted Answer

結構たくさんありますね、検索しませんでしたか？

以下は、O( n log h ) ランタイムのカップルです。nは入力ポイントの数で、hは結果の頂点の数です。

以下は、アルゴリズムへのリンクを含む 4 つの方法のデモンストレーションです。

score 2 · Accepted Answer

O（n ^ 3）バージョンは、おそらく3dハルのJarvisアルゴリズムです。このアルゴリズムを見てください、私はよく説明されていると思います：

2 に答える 2