Реализация Graham Scan в C#

Question

Я пытаюсь внедрить Graham Scan из псевдокода Wikipedia, и я столкнулся с небольшими проблемами, переводя вещи на C#. Возможно, вы не против взглянуть?

Вот что у меня есть:

public class GrahamScan 
    { 
     public static List<CoordinatesD> Scan(List<CoordinatesD> coordinateslist) 
     { 


       int coordinatesize = coordinateslist.Count; 
       CoordinatesD[] coordinatesarray = new CoordinatesD[coordinatesize]; 
       for (int i = 0; i < coordinatesize; i++) 
       { 
        coordinatesarray[i] = coordinateslist[i]; 
       } 

       //swap points[1] with the point with the lowest y-coordinate; 
       int lowestyindex = LowestY(coordinatesarray); 
       Swap(coordinatesarray[0], coordinatesarray[lowestyindex]); 

       //sort points by polar angle with points[1]; 
       coordinatesarray = SortByPolarAngle(coordinatesarray[0], coordinateslist); 


       // We want points[0] to be a sentinel point that will stop the loop. 
       coordinatesarray[0] = coordinatesarray[coordinatesize]; 

       // M will denote the number of points on the convex hull. 
       int numpointsonhull = 1; 
       for (int i = 2; i < coordinatesize; i++) 
       { 
        // Find next valid point on convex hull. 
        while(CCW(coordinatesarray[numpointsonhull-1], coordinatesarray[numpointsonhull], coordinatesarray[i]) <= 0) 
        { 
          if(numpointsonhull > 1) 
          { 
            numpointsonhull -= 1; 
          } 
          // All points are collinear 
          else if (i == coordinatesize) 
          { 
            break; 
          } 
          else 
          { 
            i += 1; 
          } 
        } 

        // Update M and swap points[i] to the correct place. 
        numpointsonhull += 1; 
        //swap(points[M],points[i]); 
        Swap(coordinatesarray[numpointsonhull], coordinatesarray[i]); 
       } 

      List<CoordinatesD> pointsonhulllist = new List<CoordinatesD>(); 

      for (int i = 0; i < numpointsonhull; i++) 
      { 
       pointsonhulllist.Add(coordinatesarray[i]); 

      } 

      return pointsonhulllist; 



     } 

     /// <summary> 
     /// Swaps two points. 
     /// </summary> 
     /// <param name="p1"></param> 
     /// <param name="p2"></param> 
     private static void Swap(CoordinatesD p1, CoordinatesD p2) 
     { 
      CoordinatesD temp = p1; 
      p1 = p2; 
      p2 = temp; 

     } 

     /// <summary> 
     /// Attempts to Sort by Polar Angle, with respect to p1. 
     /// </summary> 
     /// <param name="p1"></param> 
     /// <param name="points"></param> 
     /// <returns></returns> 
     private static CoordinatesD[] SortByPolarAngle(CoordinatesD p1, List<CoordinatesD> points) 
     { 

      CoordinatesD[] sortedpoints = new CoordinatesD[points.Count]; 
      int sortedpointiterator = 0; 

      while(true) 
      { 
       int current = 0; 
       for (int i = 0; i < points.Count; i++) 
       { 
        if (p1.PolarAngle - points[i].PolarAngle < p1.PolarAngle - points[current].PolarAngle) 
        { 
         current = i; 
        } 

       } 

       sortedpoints[sortedpointiterator] = points[current]; 
       sortedpointiterator++; 
       points.RemoveAt(current); 

       if (points.Count == 0) 
       { 
        break; 
       } 
      } 



      return sortedpoints; 
     } 
     /// <summary> 
     /// Finds the index of the CoordinateD with the lowest Y. 
     /// </summary> 
     /// <param name="coords"></param> 
     /// <returns></returns> 
     private static int LowestY(CoordinatesD[] coords) 
     { 
      int index = 0; 
      for (int i = 0; i < coords.Length; i++) 
      { 
       if(coords[i].Y < coords[index].Y) 
       { 
        index = i; 
       } 
      } 
      return index; 
     } 




     // Three points are a counter-clockwise turn if ccw > 0, clockwise if 
     // ccw < 0, and collinear if ccw = 0 because ccw is a determinant that 
     // gives the signed area of the triangle formed by p1, p2 and p3. 
     private static double CCW(CoordinatesD p1, CoordinatesD p2, CoordinatesD p3) 
     { 
      return (p2.X - p1.X) * (p3.Y - p1.Y) - (p2.Y - p1.Y) * (p3.X - p1.X); 
     } 
    } 

И это делает использование этого класса:

public class CoordinatesD : iCoordinates 
    { 
     private double latitude = 0.0; 
     private double longitude = 0.0; 

     public enum ServiceType { Google = 0, Bing = 1 }; 

     public double Latitude 
     { 
      get { return latitude; } 
     } 

     public double Longitude 
     { 
      get { return longitude; } 
     } 

     public double X 
     { 
      get { return longitude; } 
     } 

     public double Y 
     { 
      get { return latitude; } 
     } 

     public double PolarAngle { get { return CalculatePolarAngle(); } } 

     public CoordinatesD(double latitude, double longitude) 
     { 
      this.latitude = latitude; 
      this.longitude = longitude; 
     } 


     private double CalculatePolarAngle() 
     { 

      double polarangle = Math.Atan(latitude/longitude); 
      if (polarangle > 0.0) 
      { 
       return polarangle; 
      } 
      return polarangle + Math.PI; 

     } 

     public CoordinatesD Change(double changelat, double changelong) 
     { 

      CoordinatesD newCoordinates = new CoordinatesD(this.latitude + changelat, this.longitude + changelong); 

      return newCoordinates; 

     } 

     public string ToJScriptString(ServiceType service) 
     { 

      string jscriptstring = string.Empty; 

      switch (service) 
      { 
       case ServiceType.Bing: 
        jscriptstring = String.Format("new Microsoft.Maps.Location({0},{1})", this.latitude.ToString(), this.longitude.ToString()); 
        break; 
       case ServiceType.Google: 
        jscriptstring = String.Format("new google.maps.LatLng({0},{1})", this.latitude.ToString(), this.longitude.ToString()); 
        break; 
       default: 
        break;   
      } 


      return jscriptstring; 
     } 




    } 

код любит взрывать, в основном потому, что я прочитал десяток псевдо реализаций, которые все разные, и никто не объясняет вещи слишком адекватно. Я получаю ошибку за пределами массива, что, я даже не уверен, что нужно координировать или координировать + 1, или координировать - 1, или координировать + killme -> изначально это было «N» или «N» +1 ', но, как вы можете видеть, я постепенно теряю сознание этого перевода.

Answer 1

Этот вопрос вполне может быть мертв, однако он появился в «Связанных» вопросах StackOverflow, потому что я добавил реализацию C# для сканирования Грэма здесь: Graham scan issue at high amount of points. Алгоритм Википедии фактически имеет ошибки в случае коллинеарности точек и начальной минимальной точки.