title: Implementing Graham Scan to find the convex hull
body: <p>I'm trying to implement the <a href="http://en.wikipedia.org/wiki/Graham_scan#Pseudocode" rel="nofollow">Graham Scan</a> in C++ but it doesn't work and I can't find why. Any lead would be appreciated. After some tries it seems that I always have <code>m_M = 2</code> and the 2 points are the highest-y points, if that help.</p>
  
  <p>Cross product to know if it's a right turn or a left turn.</p>
  
  <pre><code>qreal Interpolation::ccw(QPointF pt1, QPointF pt2, QPointF pt3)
  {
      return (pt2.x()-pt1.x())*(pt3.y()-pt1.y()) - (pt2.y()-pt1.y())*(pt3.x()-pt1.x());
  }
  </code></pre>
  
  <p>Dot product divided by the norm to have the <code>cos</code> because sorting the angle is the same as sorting the <code>cos in [0, Pi]</code>.</p>
  
  <pre><code>qreal Interpolation::dp(QPointF pt1, QPointF pt2)
  {
      return (pt2.x()-pt1.x())/qSqrt((pt2.x()-pt1.x())*(pt2.x()-pt1.x()) + (pt2.y()-pt1.y())*(pt2.y()-pt1.y()));
  }
  </code></pre>
  
  <p>The main function:</p>
  
  <pre><code>void Interpolation::ConvexHull()
  {
      QPointF points[m_N+1]; // My number of points
      QPointF pt_temp(m_pt[0]);
      qreal angle_temp(0);
      int k_temp(0);
  </code></pre>
  
  <p>Fill the array points with <code>points[1]</code> being the lower-y point:</p>
  
  <pre><code>    for (int i(1); i &lt; m_N; ++i)
      {
          if (m_pt[i].y() &lt; pt_temp.y())
          {
              points[i+1] = pt_temp;
              pt_temp = m_pt[i];
          }
          else
          {
              points[i+1] = m_pt[i];
          }
      }
      points[1] = pt_temp;
  </code></pre>
  
  <p>Sorting the points array by angle and doing <code>points[m_N] = points[0]</code></p>
  
  <pre><code>    for (int i(2); i &lt;= m_N; ++i)
      {
          pt_temp = points[i];
          angle_temp = dp(points[1], pt_temp);
          k_temp = i;
          for (int j(1); j &lt;= m_N-i; ++j)
          {
              if (dp(points[1], points[i+j]) &lt; angle_temp)
              {
                  pt_temp = points[i+j];
                  angle_temp = dp(points[1], points[i+j]);
                  k_temp = i+j;
              }
          }
          points[k_temp] = points[i];
          points[i] = pt_temp;
      }
      points[0] = points[m_N];
  </code></pre>
  
  <p>Executing the Graham scan</p>
  
  <pre><code>    m_M = 1; // Number of points on the convex hull.
  
      for (int i(2); i &lt;= m_N; ++i)
      {
          while (ccw(points[m_M-1], points[m_M], points[i]) &lt;= 0)
          {
              if (m_M &gt; 1)
              {
                  m_M -= 1;
              }
              else if (i == m_N)
              {
                  break;
              }
              else
              {
                  i += 1;
              }
          }
          m_M += 1;
          pt_temp = points[m_M];
          points[m_M] = points[i];
          points[i] = points[m_M];
      }
  </code></pre>
  
  <p>Saving the points to <code>m_convexHull</code> which should be the list of the points on the hull with <code>ConvexHull[m_M]=[ConvexHull[0]</code></p>
  
  <pre><code>    for (int i(0); i &lt; m_M; ++i)
      {
          m_convexHull.push_back(points[i+1]);
      }
      m_convexHull.push_back(points[1]);
  }
  </code></pre>