2

問題：

与えられた : n >> k の場合、3 次元の k 辺非凸多角形に強く相関する n 個のポイント

Find : ポイントの元のジオメトリに一致する最適な凹包

試みられた解決策:

警告: 疑似コード

segments = []
for each point in image:
    #segment points into planes via comparing approximate normals
    #actual implementation is more complicated
    findSegment(image,point)
for each segment in image:
    #transform coordinate system to be a 
    #2D-plane perpendicular to the normal of segment
    transform(segment, segment.normal)
    edges = findEdges(segment)
    polygonHull = reconstructPolygon(edges)
    #transform back to original coordinate system
    transform(segment, segment.normal)

例：

 ___
|   |               |
|    \__    ==>     |   ___
|       |           |__/  /_____
|_______|          /  /   \_
                  /  /_____/
                 /

入力は、ポリゴン プレーン内にほぼ均一に分散されたランダムなポイントである高密度のポイント クラウドであり、少しノイズがあります。

出力は、3D ポイントのポリゴンの頂点になります。

私の質問は、この問題にアプローチするより良い方法はありますか? 上記の解決策の問題点は、ポイントがノイズになる可能性があることです。また、ポイントを 2D にラスタライズしてからエッジ検索を実行するのはかなりコストがかかります。

どんな指針も素晴らしいでしょう。前もって感謝します

4

3 に答える 3

2

凹んだ角が鋭すぎない場合は、ポイント セットで 3D Delaunay 三角形分割を実行してみます。境界上のポイントのボロノイ領域は、無限になるか、内側のボロノイ領域よりもはるかに長くなる傾向があります。同様に、多面体の 1 つの面に関連付けられている境界上のセルは、関連付けられている面にほぼ垂直な方向に整列する傾向があります。つまり、それらはすべて細長く、長軸はほぼ平行で、多角形の外を向いています。ちょっと準疑似コードで

Compute Delaunay triangulation
Collect long thin Voronoi regions
Partition the Voronoi regions into clusters that are nearby and nearly parallel.
Create faces normal to the axes of the Voronoi regions.

編集 これで、ポリゴンが必要であることがわかりました。上記のアプローチは機能しますが、おそらく 2 つのステップで行うのが最善です。最初に、ポリゴンが存在する平面を見つけます。ポイントの小さなサンプルの最小二乗フィットを実行するだけで十分です。ポイントを平面に投影し (これはほとんどあなたが行ってきたことです)、次に 2 次元 Delaunay 三角形分割を計算してエッジ ポイントを見つけ、上記のように続行します。

于 2010-08-10T21:57:06.540 に答える
0

まず、メッシュの表現を選択します。2D では、次の表現を使用して Python 凹包アルゴを実装しました: half-edge data structure。

次に、2D のアルゴリズム (3D に適応する必要があります) は、Edelbrunner によるアルファ形状アルゴリズムに近づけることができます。

于 2013-05-07T06:33:59.280 に答える
0

平面に投影された 3 空間内の点のコレクションの凹包を計算したいようです。2D のケースについては、ここで詳しく説明します。

于 2010-08-10T01:39:01.023 に答える