c# - 礼品包装算法

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;
        }

现在不知道如何在我的案例中使用礼品包装算法。维基百科上的伪代码 link对我来说不是很理解，所以我在这里寻求帮助。

我正在使用 C# 和 win 表单 (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  *)
        }
    }
}

适应您的私有(private)类(class)，将是您的作业。