2

パネル上の点群をに保存してから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リンクの擬似コードは私には本当に理解できないので、ここで助けを求めています。

C＃とWinフォームを使用しています（net.framework 4.0）

助けてくれてありがとう。

4

3 に答える 3

13

これを参照として使用して、コードを次に示します。

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  *)
        }
    }
}

あなたのプライベートクラスへの適応は、あなたの宿題になります。

于 2012-04-05T03:19:54.417 に答える
3

WindowsBaseのSystem.Windows.Pointクラスを使用した実装は次のとおりです。

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;
}
于 2012-04-05T03:25:15.630 に答える
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

于 2013-01-31T23:53:36.563 に答える