1

次のようなint座標のペアのリストがあります

list<pair<int,int> > coordinates;

1 つのポイント原点に最も近いポイントを見つける必要があります。

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

カスタムコンパレータオブジェクトと並べ替えで見つけることができますが、 min を使用するともっと速い方法があるのではないかと思いますか? 私は試した

class DistanceComparator{
public:
    DistanceComparator(const Point& p){origin=p;}
    inline bool operator<(std::pair<int,int> & lhs,std::pair<int,int > & rhs)
    {
        float deltaX1=lhs.first-origin.x;
        float deltaY1=lhs.second-origin.y;
        float deltaX2=rhs.first-origin.x;
        float deltaY2=rhs.second-origin.y;
        return (deltaX1*deltaX1+deltaY1*deltaY1)<(deltaX2*deltaX2+deltaY2*deltaY2);
    }
private:
    Pointorigin;
};

しかし、 < は引数を 1 つだけ取る必要があります。これを行う方法 ？

4

3 に答える 3

5

リスト全体をソートする必要があるため、ソリューションは最適ではありませんが、これは必要ありません。必要なのは最小限の要素だけで、残りを並べ替える必要はありません。調べるstd::partial_sortか、単にコマンドを実行して、それを反復することをお勧めします（並べ替えO(n)とは対照的にO(n*log(n))）。

于 2012-11-02T14:24:10.390 に答える
2

Luchian Grigore が既に述べたように、ポイントのリストを並べ替えるべきではありません。ただし、ここで構文上の問題に対処したいと思います。

他の2 つのオブジェクトを比較するクラスメンバーとして比較演算子を使用することはできません。比較演算子を定義するには、次の 2 つの方法しかありません。

  1. 左側のオペランドであるbool T::operator<(const U& rhs) constメンバー関数。this( const-reference はオプションだと思いますが、もちろん強くお勧めします。) T == Utrue である必要はないことに注意してください。

  2. 必ずしも真であるbool operator<(const T& lhs, const U& lhs) constとは限らない非メンバー関数です。T == U

したがって、必要に応じて 3 つのオブジェクトにアクセスできる比較演算子を使用することはできません。2 つのオペランドと、比較をパラメーター化できる「コンテキスト」のようなものです。

この問題を解決するために、次の 2 つの解決策を知っています (それ以上の解決策があるかもしれません)。

  1. 比較演算子の使用を開始するときに、追加パラメーターをグローバル変数として設定します。もちろん、これは非常に汚い (OOP ではグローバルは常に汚い) ため、並べ替えは再入不可になります。あまりにも汚いので、私は決してお勧めしません (しかし、それでも可能な解決策です)。したがって、ここではサンプル コードを示しません。

  2. の代わりに述語を使用しoperator <ます。これには複数の方法があります。ここに2つあります：

    c++0x / c++11 が利用可能な場合:クライアント コンテキスト (実行する場所)から追加のパラメーターを取得できるラムダ関数を使用します。std::sort

    Point origin = ...;
std::sort(..., [origin](const Point & a, const Point & b){
    return distance(a, origin) < distance(b, origin);
});

    c++0x / c++11 が利用できない場合:カスタム述語を定義して、ラムダ関数を使用せずにカスタマイズされた方法で 2 つのオブジェクトを比較できます。コンパレータ ヘルパー クラスを定義する必要があります。

    // Helper class:
struct PointDistanceComparator {
    PointDistanceComparator(Point origin) : origin(origin) {}
    bool operator() (const Point & a, const Point & b) const {
        return distance(a, origin) < distance(b, origin);
    }
private:
    Point origin;
};

// Client code:
Point origin = ...;
std::sort(..., PointDistanceComparator(origin));

    もちろん、距離の計算に平方根を使用しないようにコードを最適化することもできます。サンプルコードは、一般的な比較をパラメーター化する方法についてのアイデアを提供するだけです。

于 2012-11-02T15:08:16.257 に答える
1

座標のリストを何度もクエリする必要がある場合は、最近傍検索にKd ツリーを使用することを検討してください。これにはO(log n)時間の複雑さが伴います。Kd ツリーの構築とクエリは、約 15 ～ 20 行の (読み取り可能な) C++ コードです。Kd-tree ウィキペディアの記事 も見てくださいstd::nth_element。これを使用して、Kd-tree を効率的に構築できます (ピボット ポイントを選択し、コンテナーを分割します (左右の子、ウィキペディアの記事の python コードを参照))。 .

更新: K 最近傍探索を使用してC++ N 次元 Kd ツリーの実装を作成します。使用方法を示すいくつかの単体テストが含まれています。

于 2012-11-03T03:12:06.253 に答える