礼品包装算法

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