ポイントクラウドの配列があります（独自の領域にあると判断されたポイントのクラスター）。
目標は、これらの個々のクラスターを結合することです。
私。交差
ii. お互いからの最小距離内
チェックiiはこれをより困難にします。これらのポイント クラウドをすばやく処理するために、AABB (X 軸に沿って整列された軸整列バウンディング ボックス) を作成しています。
私の現在の方法は、分離軸定理のいくつかのプロパティを使用することです。
- ポイントクラウドごとに AABB を作成する
- 各 AABB について、これらをランダムな軸に射影し、これらの線形射影をこの行 o(nlog(n)) のどこにあるかによって並べ替えることによって、それらが重複しているかどうかを確認します。次に、このリストを調べて、SAT を使用して交差 O(N) を確認します。ほとんどの AABB の線形射影は重ならないため、交差しません。交差するものは手動で確認できます (1D で重ならないことは交差がないことを保証するためですが、その逆は当てはまりません)。
最後の部分は私が立ち往生しているところです。上記の 1D 投影は、交差の O(n^2) ペアワイズ チェックを回避するために行われました。しかし、特定のしきい値内にあるが交差していない凸多角形を結合するために、O(N^2) ペアワイズ チェックを回避する方法がわかりません。
各ペアごとの組み合わせをチェックせずに、特定の距離内にあるすべての凸多角形を組み合わせてツリーまたはグラフを作成する方法はありますか?
1 と 2 の私の手順を使用する場合、残りのポイント クラウド/AABB が交差していないと想定できます。
編集
threshold/2潜在的な解決策は、AABB幅と高さにを追加し、交差をチェックすることです。それらが交差する場合、実際の交差 (AABB では高速) と 2 つの間の最小距離の両方を確認できます。