点群があり、コード内の点の特定のパターンの発生を検出したいと考えています。
3D 空間に 1000 個のポイントがあり、L の各セグメントが特定の長さを持つ「L」形状を形成する 3 つのポイントのすべてのインスタンスを検出したいとします。ポイント クラウドは完全に一致しない場合がありますが、非常に近い場合があります (つまり、ポイント クラウドでは、「L」のセグメントの長さが理想よりもわずかに長い/短い場合があります)。
私の最初のアイデアは次のようなものでした：
- 検出しようとしている形状のすべてのポイント間の距離を記録します
- 空の「潜在的な形状」を作成します
- 潜在的な形状の各点について、パート 1 で見つかった距離にある/近い距離にあるすべての点を調べます)
- ポイントが見つかったら、それを潜在的な形状に追加し、すべてのポイントが得られるまでパート 3) を繰り返します。次に、ポイント間の角度をチェックして、形状が実際に正しいことを確認します。正しくない場合は、次のポイントに進み、最初からやり直します
問題は、このアプローチの最悪の場合の実行時間がひどいことです。理想的には、特定のポイントから距離最小と距離最大の間にあるすべてのポイントを検索するためのクエリを高速化するために、ある種のデータ構造が必要です。役立つデータ構造を教えてください。
アクセス時間を短縮するために、すべてのポイントを octree に入れることを考えていました。
実行時間を改善する方法について他にアドバイスはありますか? 物事をスピードアップするためのヒューリスティック？
注：私が見つけようとしている形状は可変です。それらは常に「L」であるとは限りません。ハフ変換を調べてみましたが、線や円などの特定の所定の形状を検出する場合にのみ役立つようです。