Jarvis algorithm (gift-wrapping) or graham-scan - C#

601 views Asked by At

I have a list of Shapes and I have to make a convex hull around them. I tried to do a gift-wrapping algorithm (Jarvis). So far I have foud a plenty of pseudocodes and I understand the logic, but I can't program it. Could only do the 1st step - finding the lowest & "leftest" shape.

        List<Point> Ob = new List<Point>();
        Point p = new Point();
        for (int i = 0; i < L.Count - 1; i++)
        {
            if (L[i].CoordinateX < L[i + 1].CoordinateX) p.X = (int)L[i].CoordinateX;
            if (L[i].CoordinateY < L[i + 1].CoordinateY) p.Y = (int)L[i].CoordinateY;
        }
        Ob.Add(p);

So then I tried to find the smallest angle. My logic was that the smaller angle the smaller the cos of this angle

        double angle = 0, angle1 = 0;
        int num = 0;
        for (int k = 0; k < L.Count - 1; k++)
        {
            angle = Math.Cos((Math.Sqrt(Math.Pow((L[k].CoordinateX - p.X), 2) + Math.Pow((p.Y - L[k].CoordinateY), 2))) / (Math.Sqrt(Math.Pow((L[k].CoordinateX - p.X), 2) + Math.Pow((L[k].CoordinateY - p.Y), 2))));
            angle1 = Math.Cos((Math.Sqrt(Math.Pow((L[k + 1].CoordinateX - p.X), 2) + Math.Pow((p.Y - L[k + 1].CoordinateY), 2))) / (Math.Sqrt(Math.Pow((L[k + 1].CoordinateX - p.X), 2) + Math.Pow((L[k + 1].CoordinateY - p.Y), 2))));
            if (angle < angle1) num = k;
        }
        Point p1 = new Point((int)L[num].CoordinateX, (int)L[num].CoordinateY);
        e.Graphics.DrawLine(new Pen(Color.Black), p, p1);

But this code ended in this added 3 circles first, then added 1 more and so on. Obviously this doesn't make any sense. And this

Do you know any realizations of Graham or Jarvis to look at?

0

There are 0 answers