Алгоритм Джарвиса (упаковка подарков) или сканирование Грэма - C # - PullRequest
Новая
       28

Алгоритм Джарвиса (упаковка подарков) или сканирование Грэма - C #

0 голосов
/ 12 ноября 2018

У меня есть список фигур, и я должен сделать выпуклую оболочку вокруг них. Я пытался сделать алгоритм упаковки подарков (Джарвис). Пока у меня много псевдокодов, и я понимаю логику, но не могу ее запрограммировать. Может сделать только 1-й шаг - найти самую низкую и «левую» форму. 

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

Итак, я попытался найти самый маленький угол. Моя логика заключалась в том, что чем меньше угол, тем меньше cos этого угла 

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

Но этот код заканчивался этим добавлено 3 круга сначала , затем добавлено еще 1 и и так далее . Очевидно, это не имеет никакого смысла. И это

Знаете ли вы какие-либо реализации Грэма или Джарвиса, на которые можно посмотреть?

...