Реализация Graham Scan, чтобы найти выпуклый корпус

Question

Я пытаюсь реализовать Graham Scan в C++, но он не работает, и я не могу найти причину. Любое руководство будет оценено по достоинству. После некоторых попыток кажется, что у меня всегда есть m_M = 2, а 2 точки - это наивысшие точки, если это поможет.

Перекрестный продукт, чтобы узнать, является ли это поворот вправо или левый поворот.

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()); 
} 

Dot продукт делится на норму, чтобы иметь cos, потому что сортировка угол такой же, как сортировка cos in [0, Pi].

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())); 
} 

Основная функция:

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

Заполните точки массива с points[1] быть ниже-й пункт:

for (int i(1); i < m_N; ++i) 
    { 
     if (m_pt[i].y() < pt_temp.y()) 
     { 
      points[i+1] = pt_temp; 
      pt_temp = m_pt[i]; 
     } 
     else 
     { 
      points[i+1] = m_pt[i]; 
     } 
    } 
    points[1] = pt_temp; 

Сортировка массива точек по углу и делает points[m_N] = points[0]

for (int i(2); i <= m_N; ++i) 
    { 
     pt_temp = points[i]; 
     angle_temp = dp(points[1], pt_temp); 
     k_temp = i; 
     for (int j(1); j <= m_N-i; ++j) 
     { 
      if (dp(points[1], points[i+j]) < 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]; 

Выполнение Грэма сканирования

m_M = 1; // Number of points on the convex hull. 

    for (int i(2); i <= m_N; ++i) 
    { 
     while (ccw(points[m_M-1], points[m_M], points[i]) <= 0) 
     { 
      if (m_M > 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]; 
    } 

Сохранение точек в m_convexHull, которые должны быть в списке точек на корпусе с ConvexHull[m_M]=[ConvexHull[0]

for (int i(0); i < m_M; ++i) 
    { 
     m_convexHull.push_back(points[i+1]); 
    } 
    m_convexHull.push_back(points[1]); 
} 

Answer 1

Я нашел проблему. Он заключен в предложении:

Точечный продукт, деленный на норму, чтобы иметь cos, потому что сортировка угла такая же, как и сортировка cos в [0, Pi].

Чем меньше угол, тем выше потому, так что я просто должен был изменить эту строку кода:

  if (dp(points[1], points[i+j]) < angle_temp) 

к:

  if (dp(points[1], points[i+j]) > angle_temp) 

и теперь он работает отлично!