5

最も近い隣人を見つけるためのアルゴリズムの 1 つにSpace Partitioningがあります。それはどのように機能しますか？

点 (x 座標と y 座標) の 2D セットがあり、点 (a,b) が与えられているとします。このアルゴリズムはどのようにして最近傍を見つけますか?

4

2 に答える 2

4

空間分割は、実際には密接に関連するアルゴリズムのファミリーであり、アプリケーションがポイントまたはポリゴンをより簡単に処理できるように空間を分割します。

私はあなたの問題を解決する多くの方法があると思います。ソリューションを構築するのにどれほど複雑なのかわかりません。簡単な方法は、おそらくスペースを2にカットする二分木を構築することです。すべてのポイントはいくつかの中央平面に分割されます。ポイントがなくなるまで再帰的に細分化してツリーを構築します。

ツリーをトラバースするたびに検索領域が絞り込まれるため、最近傍の検索が最適化されます。

いくつかの文献では、これをkdツリーと呼んでいます

于 2009-11-11T08:18:52.537 に答える
2

次の 2 つのビデオが役に立ちます。

于 2011-06-03T12:18:41.913 に答える