在c＃中對基點的角度進行點排序＃

Question

我試圖在C＃中實現用於查找凸包的Graham算法。它包括按照它們與基點的角度對點進行排序的步驟。我想用Array.Sort方法使用從Comparer繼承的類來實現它。

這裏是類

class ReversePolarSorter : Comparer<Point> 
    { 
     double e = 0.000001; 
     double m_baseX; 
     double m_baseY; 
     public ReversePolarSorter(Point basePoint) 
     { 
      m_baseX = basePoint.X; 
      m_baseY = basePoint.Y; 
     } 

     public override int Compare(Point a, Point b) 
     { 


      double angleA = Math.Atan2(a.Y - m_baseY, a.X - m_baseX); 
      double angleB= Math.Atan2(b.Y - m_baseY, b.X - m_baseX); 
      int result; 
      if (Math.Abs(angleA - angleB) < e) 
       result= 0; 
      else 
       result= angleA.CompareTo(angleB); 

      return result; 
     } 
    } 

然後我使用它與

Comparer<Point> sorter = new ReversePolarSorter(coords[m_pointsNumber-1]); 
Array.Sort<Point>(coords, 0, m_pointsNumber - 2, sorter); 

COORDS排序是點的陣列。 m_pointsNumber是許多點。
m_pointsNumber-1是用於計算角度的基點。

它沒有按正確的順序排序，我看不到問題。如果有人能夠確定它，我將不勝感激。

Answer 1

我認爲使用epsilon的比較實施不正確。

正如我們所知，如果a == b和b == c，然後a == c。但是這種實現可能導致a == b,b == c，但是a < c，這將打破排序算法。

既然你有一個基點，可以使用舍入，而不是小量：

class ReversePolarSorter : Comparer<Point> 
{ 
    const int precision = 6; 
    double m_baseX; 
    double m_baseY; 
    public ReversePolarSorter(Point basePoint) 
    { 
     m_baseX = basePoint.X; 
     m_baseY = basePoint.Y; 
    } 

    double GetAngle(Point p) 
    { 
     return Math.Round(Math.Atan2(p.Y - m_baseY, p.X - m_baseX), precision); 
    } 

    public override int Compare(Point a, Point b) 
    { 
     return GetAngle(a).CompareTo(GetAngle(b)); 
    } 
} 

另外，還要注意的Array.Sort的第三個參數是長度，所以如果m_pointsNumber是點數和點在索引m_pointsNumber - 1是基準點，那麼就應該通過m_pointsNumber - 1如長度：

Array.Sort(coords, 0, m_pointsNumber - 1, sorter);