Gift wrapping algorithm

Question

I saved group of points on my panel to List<MyVector> savedPoints, then I calculated the the point with lowest coordinate 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];
    }

after this I made a method to calculate polar angles :

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

now don't know how to use Gift wrapping algorithm in my case. The pseudocode on WikiPedia link is not really understandable for me, so I'm asking for help here.

I'm using C# and win forms (net.framework 4.0)

Thanks for any help.

score 13 · Accepted Answer · edited May 23 '17 at 12:17

Using this as a reference, here is teh code:

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

adaptation to your private classes, would be your homework.

@Ivo, did you ever figure out why and what's the fix? – wolfrevo Feb 05 '16 at 09:58 — wolfrevo, Feb 05 '16 at 09:58

score 3 · Answer 2 · answered Apr 05 '12 at 03:25

Here is an implementation using the System.Windows.Point class in 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;
}

score 3 · Answer 3 · edited May 23 '17 at 12:17

For Gift Wrapping algorithm implementation, it is advisable that one uses Left test technique

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

Using this(Left test) comparison technique helps us in wrapping the gift faster, so to speak.

Never ever use arc tangent calculations, it will impact the run times in a big way.

Reference: Left test technique mentioned here - https://stackoverflow.com/a/1560510/1019673

Gift wrapping algorithm

3 Answers3