title: Optimization of a clockwise sort algorithm
body: <p>So this is an optimization question, which I could not find answered.</p>
  
  <p>I have written some code for computing the convex hull of a given set of random points. For comparative purposes, I have made my own, slow O(n³) algorithm, using some old OpenGL stuff to visualize it. Because of the nature of the slow convex hull algorithm, the points are not sorted at all. So the sort takes place just after the computation of the CH. </p>
  
  <p>My problem is that up till 1000 points, I have a visual result in less than a second. But for 10000 points, it takes over 15-20 minutes (I have not waited beyond that). <em>However</em> if I skip the sorting code and let opengl display the convex hull vertices unsorted, it takes less than a minute. So it's the ClockWise sorting that's eats up all that time. Check the code (some names don't make sense as they are defined elsewhere) :</p>
  
  
  
  <pre class="lang-or-tag prettyprint-override"><code>// 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&lt;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&lt;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&lt;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;
  </code></pre>
  
  <p>The display part:</p>
  
  <pre class="lang-or-tag prettyprint-override"><code>glColor3f(0.8, 0.2, 0.2);
  glPointSize(3);
  glBegin(GL_LINE_LOOP);
      for (int i=0;i&lt;count;i++){
          glVertex2f(convexHull.at(i).at(0),convexHull.at(i).at(1));
      }
  glEnd();
  </code></pre>
  
  <p>From what I've seen, this approach (by comparing cross products) is the most efficient. However, before this I wrote some filthy code which actually was faster, as it gave me a visual result within 8 minutes. I don't want to keep that because it's too dirty and long, this one is cleaner but very slow (if it actually works at all....). So, am I bound to wait so much for a CW sort of 10000 convex points, or there is something I am missing?  </p>
  
  <p>I'd appreciate any thoughts, let me know if I need to include anything else.</p>