ポイントクラウド間の距離を効率的に見つける

Question

私は2点の雲（3D空間内の点の集合）と反復アルゴリズムを持っています。雲の一つ（のは、それを呼び出してみましょう）各反復別に一定であるが（B（I）それを呼び出す）各反復でわずかに異なっている（それはB（I + 1）は、と異なることを意味しますB（i）のみいくつかの点で）。すべての反復において、Aの各点について、iのアルゴリズムで、最も近い点をB（i）から見つける必要があります。

私の質問は、どうすればこれらの距離をできるだけ速く計算することができますか？ここで

は、私はすでに試したものです：

• ブルートフォース・コンピューティング（とB（I）からポイントの各ペアのためのすべての距離を計算） - 絶対に非効率的に。各反復で
• B（I）用KD-ツリーを構築し、その後から各点の最も近い点を見つける - 私はそれぞれにKD-ツリーを再構築する必要がありますので、より高速なブルートフォース、その後、しかし（まだ計算コストが高いです繰り返し）。

は、それは私が実際に利用すべきであるように思えることB（I）とB（I + 1）は、互いにわずかに異なりますが、私はまだ良い解決策を考え出すことはできません。前もって感謝します。

Answer 1

Aの各点について、以前の反復B（i）で最も近い点の記録を保持します。反復で

I + 1、iとI + 1、及びAの各点についてB.

においても、それぞれの新しいポイント間削除または変更されたBの各点のリストを作る：

は

• Bの直近の点が変更または削除されていない場合、AからB（i + 1）の新しい点の最も近い点までの距離を計算し、B私）。
• B（I）の前の最も近い点が変更または削除された場合、あなたはBでのポイントのいずれかにから最も近い距離を計算する必要があります（I + 1）

あなたが使用することができますKDツリーや、これを高速化するのが好きな空間データ構造はありませんが、最適化は最初のケースから来ています。 KDツリーでは削除が可能なので、各繰り返しごとに全体を最初から再構築する必要はありません。