Geek asks and answers

Clockwise sorting algorithm optimization

So, this is an optimization question to which I could not find an answer.

I wrote some code to calculate the convex hull of a given set of random points. For comparative purposes, I made my own slow O (n³) algorithm using some old OpenGL visualization tools. Due to the nature of the slow convex hull algorithm, points are not sorted at all. Thus, sorting occurs immediately after calculating CH.

My problem is that up to 1000 points I get a visual result in less than a second. But for 10,000 points, it takes more than 15-20 minutes (I did not wait for this). However, if I skip the sort code and let opengl display the convex vertices of the case, unsorted, it takes less than a minute. So sort the ClockWise that has been eating all this time. Check the code (some names do not make sense, as they are defined elsewhere):

// 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;

Displayed Part:

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 , - ?

, , - .

+5
2

, . 2D- (, ) () , .

, , O (N ^ 2) , . , 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);
}

, :

  • : pts.
  • Point ( ) x y (a operator <), x , y.
  • , O (N * log (N)), , , O (N ^ 2).
  • . , .
  • , X ( !)
  • , .
  • , , . , <= 0 >= 0 while < 0 > 0 .

: CH, ( .)

+3

Bubble Sort, O (n 2). O (n log (n)), STL 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

EDIT:

. :

#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));
  }
}
+2

More articles:


All Articles