그레이엄 스캔을 C#으로 구현하기

Question

위키피디아 의사 코드에서 그레이엄 스캔을 구현하려고하는데, 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로 지정하거나 좌표를 지정하지 않습니다. 원래는 'N'또는 'N'입니다. +1 '을 보았지만 알 수 있듯이 나는이 번역에 대한 생각을 서서히 잃어 가고있다.

Answer 1

이 질문은 잘 될지도 모르지만 StackOverflow의 "관련"질문에 나타났습니다. 여기에 그레이엄의 C# 구현을 추가했기 때문에 여기에 Graham scan issue at high amount of points을 입력하십시오. Wikipedia 알고리즘은 실제로 서로 공 선적 인 점과 시작점의 경우에 버그가 있습니다.