2

我有一个形状列表，我必须在它们周围制作一个凸包。我试着做一个礼物包装算法（Jarvis）。到目前为止，我已经找到了大量的伪代码并且我理解了逻辑，但我无法对其进行编程。只能做第一步 - 找到最低和“最左边”的形状。

        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个，依此类推。显然这没有任何意义。而这

你知道格雷厄姆或贾维斯的任何实现吗？

4

0 回答 0