algorithm - 3D 点群内で単純な形状を見つける

Question

たとえば、100 個の 3D ポイントのポイント クラウド内の 5 つの剛体で同一平面上にあり、同一直線上にないポイントによって定義される形状を見つける最も効率的な方法は何ですか?

Answer 1

ブルートフォースアプローチ

擬似コード:

Find all possible three point tuples from your set of points.
Every three-tuple now defines a plane.
For all planes:
   filter the set of points for points that lie in the plane
   if you have five or more points remaining, return the first five and exit  
return NOT_FOUND and exit

このアプローチの複雑さは、O(n!)を意味する階乗であることに注意してください。

たとえば、100 ポイントのセットの場合、約 1,700 万の共平面性チェックを行う必要があり、1,000 ポイントの場合、約 1,700 億の共平面性チェックを行う必要があります。

Answer 2

5 点を選択して形状を見つけることができます。100C5で十分です。組み合わせを効率的に計算する方法は、そのアルゴリズムを見つけることができます。サンプル実装はこちらから入手できます