0

後でcollection.pointsCloserThanDistance(float d、float []座標)のようなメソッドを効率的に呼び出すことができるように、2dポイントのコレクションを保持するための適切なデータ構造は何ですか? - このメソッドは、指定された座標までのすべてのポイントの距離が d 以下であるリストを返します。

(また、そのメソッドの実装はどうなりますか?)

最も単純でおそらくあまり良くない解決策は、標準配列であり、すべてのポイントを指定された座標と比較します。これは O(n)、n = ポイントの数です。しかし、O(m), m = 与えられた座標までの距離が与えられた値以下である点の数を持つことが可能かもしれません。

4

1 に答える 1

4

kdツリーのような「スペースパーティション」データ構造が必要です。

于 2012-09-24T01:51:34.957 に答える