6

Point非常に単純なクラスへのポインターのベクトルがあります。

class Point{
public:
    float x;
    float y;
    float z;
};

STL を使用して参照点に最も近いオブジェクトを見つけるにはどうすればよいですか?
最初にベクトルをソートする必要がありますか、それともより効率的な方法がありますか?

4

4 に答える 4

7

並べ替えには時間がかかるO(n*log(N))ため、あまり効率的ではありません。O(n)要素を繰り返し処理し、最適な一致を記憶するだけで、それを実行できます。

for_eachfromを使用し<algorithm>て、最も近い要素を追跡し、で完了する関数を定義できますO(n)。

min_elementまたは、からも使用できる可能性があります<algorithm>。

于 2012-06-25T13:55:39.150 に答える
1

ここでの基本的な質問は、単一のポイント セットに対してクエリを実行する頻度です。

セット内の最も近いポイントを 1 回見つける場合は、@Lucian が正しいです。ポイントをソートせずに、線形検索を実行して正しいポイントを見つけることもできます。

同じポイント セットに対して比較的多数のクエリを実行する場合は、ポイント データを整理してクエリ速度を向上させることをお勧めします。@izomorphius はすでに kd ツリーについて言及していますが、これは間違いなく良い提案です。もう 1 つの可能性 (確かに非常に似ています) は、oct-tree です。この 2 つの中で、oct-tree の方がかなり理解しやすいと思います。理論的には、kd ツリーは (平均して) わずかに効率的であるはずですが、大きな違いは見たことがありません。

ただし、kd ツリーや oct-tree のようなものを構築するのはそれほど遅くないので、構築を正当化するために一連のポイントに対して非常に多くのクエリを実行する必要はありません。明らかに 1 つのクエリでは正当化できず、おそらく 2 つのクエリでも正当化されませんが、Luchian が意味することとは反対に、O(N log N) (たとえば) はそれほど遅くはありません。大まかに言えば、log(N) は数値 N の桁数であるため、O(N log N) は O(N) よりもそれほど遅くはありません。つまり、データを整理して各クエリを高速化することを正当化するために、特に多数のクエリは必要ありません。

于 2012-06-25T14:10:03.440 に答える
0

Quadtreehttp ://en.wikipedia.org/wiki/Quadtreeの使用を試みることができます

または同様のもの。

于 2012-06-25T16:11:10.647 に答える