5

ですから、これは最適化の質問であり、答えを見つけることができませんでした。

与えられたランダムな点のセットの凸包を計算するためのコードをいくつか書きました。比較のために、古いOpenGLのものを使用して視覚化する、独自の低速O（n³）アルゴリズムを作成しました。遅い凸包アルゴリズムの性質上、ポイントはまったくソートされません。したがって、ソートはCHの計算の直後に行われます。

私の問題は、1000ポイントまで、1秒未満で視覚的な結果が得られることです。しかし、10000ポイントの場合、15〜20分以上かかります（それ以上待つことはありません）。ただし、並べ替えコードをスキップして、openglに凸包の頂点を並べ替えずに表示させると、1分もかかりません。つまり、ClockWiseの並べ替えが常に消費されます。コードを確認してください（他の場所で定義されているため、意味をなさない名前もあります）：

// This code actually compares every pair iteratively with respect to the center point
// Consider a given vector "convex", which contains all the convex hull points unsorted

.
..
...
....

int avgx,avgy,sumx=0,sumy=0;

for (int i=0;i<convex.size();i++){
    sumx+=convex.at(i).at(0);
    sumy+=convex.at(i).at(1);
}

avgx=sumx/(convex.size()/2.0); //something like an internal point
avgy=sumy/(convex.size()/2.0);

sort(convex.begin(),convex.end()); //x-sort 
int det,tempx,tempy;
for (int i=0;i<convex.size()-1;i++){
    x1=convex.at(i).at(0);
    y1=convex.at(i).at(1);
    x2=convex.at(i+1).at(0);
    y2=convex.at(i+1).at(1);
    det=(x1-avgx)*(y2-avgy)-(x2-avgx)*(y1-avgy); 
    if (det<0){ //on which side of O-X1 lies X2?
        tempx=convex.at(i).at(0); //swapping points 
        tempy=convex.at(i).at(1);
        convex.at(i).at(0)=convex.at(i+1).at(0);
        convex.at(i).at(1)=convex.at(i+1).at(1);
        convex.at(i+1).at(0)=tempx;
        convex.at(i+1).at(1)=tempy;
        i=-1; //check again the new vector from the beginning
    }
    }
return convex;

表示部分：

glColor3f(0.8, 0.2, 0.2);
glPointSize(3);
glBegin(GL_LINE_LOOP);
    for (int i=0;i<count;i++){
        glVertex2f(convexHull.at(i).at(0),convexHull.at(i).at(1));
    }
glEnd();

私が見たところ、このアプローチ（外積を比較することによる）が最も効率的です。ただし、この前に、8分以内に視覚的な結果が得られたため、実際にはより高速な不潔なコードを作成しました。汚れがひどくて長いので、それを維持したくありません。これはきれいですが、非常に遅いです（実際に機能する場合は...）。それで、私はCWのような10000の凸点を待つ必要がありますか、それとも私が見逃しているものがありますか？

何か考えていただければ幸いです。他に何か含める必要がある場合はお知らせください。

4

2 に答える 2

3

一般的に言って、この問題は少し奇妙です。ほとんどの2D凸包アルゴリズム（私が知っているすべて）は、時計回りまたは反時計回りの順序でポイント（頂点）のリストを提供します。または、そうするために簡単に変更できます。

いずれにせよ、 O（N ^ 2）以上で実行されるいくつかの優れた2D凸包決定方法があるため、それらの1つを使用して、データを時計回りに「ソート」できます。私が言っているのは、データに対してCHアルゴリズムを実行し、希望する順序で結果を取得できるということです。

これが私がうそをついたサンプルコードで、あなたが望むことをするだろうと思います：

#define TURN_DIR(p1,p2,p3)  (p1.x * p2.y - p1.y * p2.x + \
                             p2.x * p3.y - p2.y * p3.x + \
                             p3.x * p1.y - p3.y * p1.x)
#define LAST(cntnr)         (cntnr).back()
#define BEFORE_LAST(cntnr)  (cntnr)[(cntnr).size() - 2]

void ConvexHull (std::vector<Point> & pts)
{
    std::sort (pts.begin(), pts.end());

    std::vector<Point> lower, upper;
    for (unsigned i = 0; i < pts.size(); ++i)
    {
        while (lower.size() > 1 && TURN_DIR(BEFORE_LAST(lower), LAST(lower), pts[i]) <= 0)
            lower.pop_back ();
        while (upper.size() > 1 && TURN_DIR(BEFORE_LAST(upper), LAST(upper), pts[i]) >= 0)
            upper.pop_back ();

        lower.push_back (pts[i]);
        upper.push_back (pts[i]);
    }

    upper.insert (upper.end(), lower.rbegin() + 1, lower.rend() - 1);
    pts.swap (upper);
}

考慮すべき点がいくつかあります。

  1. 上記のコードは入力を受け取り、同じ引数で出力を返しますpts。
  2. 構造体は、Point2つのパブリックメンバーxと、を含む単純な構造体（またはクラス）であり、最初と次にに基づいて非常に単純にそれらを比較する小yなり演算子（an ）です。operator <xy
  3. 上記のコードの実行時間はO（N * log（N））だと思いますが、確かにO（N ^ 2）より悪くはありません。
  4. 返されるポイントは時計回りになります。反時計回りにしたい場合は、最後の2行だけを変更する必要があります。
  5. このコードは、すべてのポイントが同じX座標を持っている場合を処理しません（私は思います！）
  6. それ以外は、これは機能的で高速かつシンプルな2D凸包の実装です。
  7. 同じ行にある入力に連続するポイントがある場合、この実装はそれらを削除します。それが必要ない場合は、ループ内のテスト<= 0と>= 0テストをそれぞれとに置き換えることができます。while< 0> 0

これを強調しておきます。上記のコードはCHの実装ですが、これを使用して、ポイントを時計回りに巻く順序で並べ替えることができます（すでに凸包を形成している場合）。

于 2013-03-10T02:32:36.173 に答える
3

O（n 2 ）であるバブルソートを実装しました。適切な比較ファンクターでSTLを使用すると、O（n log（n））を取得できます。sort

これが最初の取り組みです。非推移的なコンパレータを使用しますが、私のテストケースでは機能するようで、一般的に正しいと思います。

struct clockwise : public binary_function<vector<int>, vector<int>, bool>
{
  bool operator()(vector<int> A, vector<int> B)
  {
    int det=(A[0]-avgx)*(B[1]-avgy)-(B[0]-avgx)*(A[1]-avgy);
    return(det<0);
  }

  static int avgx, avgy;
};

int clockwise::avgx = 0;
int clockwise::avgy = 0;

...

int clockwise::avgx=sumx/(convex.size()/2.0);
int clockwise::avgy=sumy/(convex.size()/2.0);
sort(convex.begin(),convex.end(), clockwise()); //clockwise-sort

編集：

非推移的な比較器は良い考えではありませんでした。これはより信頼性があります：

#include <math.h>

...

struct clockwise : public binary_function<vector<int>, vector<int>, bool>
{
  bool operator()(vector<int> A, vector<int> B)
  {
    return(atan2(A[0]-avgx, A[1]-avgy) < atan2(B[0]-avgx, B[1]-avgy));
  }
}
于 2013-03-10T03:23:35.030 に答える