禮品包裝算法

Question

我救點的組我的面板上List<MyVector> savedPoints，然後我計算出的點與最低座標y：在此之後

public void searchLowest() 
    { 
     MyVector temp; 
     double ylon = savedPoints[0].getY(); 
     for (int i = 0; i < savedPoints.Count; i++) 
     { 
      if (savedPoints[i].getY() > ylon) 
      { 
       ylon = savedPoints[i].getY(); 
       lowest = i; 
      } 
     } 

     temp = savedPoints[lowest]; 
    } 

我做了計算極角的方法：

public static double angle(MyVector vec1, MyVector vec2) 
     { 
      double angle = Math.Atan2(vec1.getY() - vec2.getY(), vec1.getX() - vec2.getX()); 
      return angle; 
     } 

現在不知道如何在我的情況下使用禮品包裝算法。 WikiPedia link上的僞代碼對我來說是不可理解的，所以我在這裏尋求幫助。

我使用C＃，贏得形式（net.framework 4.0）

感謝您的幫助。

Answer 1

使用this作爲參考，在這裏是前述代碼：

namespace GiftWrapping 
{ 
    using System.Drawing; 
    using System; 
    using System.Collections.Generic; 
    using System.Linq; 
    using System.Text; 

    class Program 
    { 
     static void Main(string[] args) 
     { 
      List<Point> test = new List<Point>(
       new Point[] 
        { 
         new Point(200,200), new Point(300,100), new Point(200,50), new Point(100,100), 
         new Point(200, 100), new Point(300, 200), new Point(250, 100), 
        }); 

      foreach (Point point in ConvexHull(test)) 
      { 
       Console.WriteLine(point); 
      } 

      Console.ReadKey(); 

     } 

     public static List<Point> ConvexHull(List<Point> points) 
     { 
      if (points.Count < 3) 
      { 
       throw new ArgumentException("At least 3 points reqired", "points"); 
      } 

      List<Point> hull = new List<Point>(); 

      // get leftmost point 
      Point vPointOnHull = points.Where(p => p.X == points.Min(min => min.X)).First(); 

      Point vEndpoint; 
      do 
      { 
       hull.Add(vPointOnHull); 
       vEndpoint = points[0]; 

       for (int i = 1; i < points.Count; i++) 
       { 
        if ((vPointOnHull == vEndpoint) 
         || (Orientation(vPointOnHull, vEndpoint, points[i]) == -1)) 
        { 
         vEndpoint = points[i]; 
        } 
       } 

       vPointOnHull = vEndpoint; 

      } 
      while (vEndpoint != hull[0]); 

      return hull; 
     } 

     private static int Orientation(Point p1, Point p2, Point p) 
     { 
      // Determinant 
      int Orin = (p2.X - p1.X) * (p.Y - p1.Y) - (p.X - p1.X) * (p2.Y - p1.Y); 

      if (Orin > 0) 
       return -1; //   (* Orientation is to the left-hand side *) 
      if (Orin < 0) 
       return 1; // (* Orientation is to the right-hand side *) 

      return 0; // (* Orientation is neutral aka collinear *) 
     } 
    } 
} 

適應你的私有類，將是你的功課。

Answer 2

下面是使用System.Windows.Point類WindowsBase實現：

public struct PolarVector { 
    public double Radius { get; set; } 
    public double Angle { get; set; } 

    public override string ToString() { 
     return "{" + Radius + "," + Angle + "}"; 
    } 
} 

private static void Main(string[] args) { 
    var points = new[] { 
          new Point {X = 0, Y = 0}, 
          //new Point {X = 2, Y = 0}, 
          new Point {X = 0, Y = 2}, 
          new Point {X = 1.5, Y = 0.5}, 
          new Point {X = 2, Y = 2}, 
         }; 
    foreach(var point in ConvexHull(points)) { 
     Console.WriteLine(point); 
    } 
    Console.WriteLine(); 
    if(Debugger.IsAttached) { 
     Console.WriteLine("Press any key to exit..."); 
     Console.ReadKey(); 
    } 
} 

public static IList<Point> ConvexHull(IList<Point> points) { 
    var pointOnHull = LeftMost(points); 
    var pointsOnHull = new List<Point>(); 
    Point currentPoint; 
    do { 
     pointsOnHull.Add(pointOnHull); 
     currentPoint = points[0]; 
     foreach(var nextPoint in points.Skip(1)) { 
      if (currentPoint == pointOnHull || IsLeft(nextPoint, pointOnHull, currentPoint)) { 
       currentPoint = nextPoint; 
      } 
     } 
     pointOnHull = currentPoint; 
    } 
    while (currentPoint != pointsOnHull[0]); 
    return pointsOnHull; 
} 

private static Point LeftMost(IEnumerable<Point> points) { 
    return points.Aggregate((v1, v2) => v2.X < v1.X ? v2 : v1); 
} 

private static bool IsLeft(Point nextPoint, Point lastPoint, Point currentPoint) { 
    var nextVector = ToPolar(nextPoint, lastPoint); 
    var currentVector = ToPolar(currentPoint, lastPoint); 
    return nextVector.Radius != 0 && Normalize(nextVector.Angle - currentVector.Angle) > 0; 
} 

private static PolarVector ToPolar(Point target, Point start) { 
    var vector = target - start; 
    return new PolarVector { Radius = Math.Sqrt((vector.Y * vector.Y) + (vector.X * vector.X)), Angle = Math.Atan2(vector.Y, vector.X)}; 
} 

private static double Normalize(double radians) { 
    while(radians > Math.PI) { 
     radians -= 2*Math.PI; 
    } 
    while (radians < -Math.PI) { 
     radians += 2*Math.PI; 
    } 
    return radians; 
} 

Answer 3

對於禮品包裝算法的實現，這是可取的做法是一個使用左測試技術

// Left test implementation given by Petr 
    private static int Orientation(Point p1, Point p2, Point p) 
    { 
     // Determinant 
     int Orin = (p2.X - p1.X) * (p.Y - p1.Y) - (p.X - p1.X) * (p2.Y - p1.Y); 

     if (Orin > 0) 
      return -1; //   (* Orientation is to the left-hand side *) 
     if (Orin < 0) 
      return 1; // (* Orientation is to the right-hand side *) 

     return 0; // (* Orientation is neutral aka collinear *) 
    } 

使用此（左測）比較技術可以幫助我們更快地包裝禮物，可以這麼說。

千萬不要使用反正切計算，它會大大影響運行時間。

參考：左測試技術，這裏所說的 - https://stackoverflow.com/a/1560510/1019673