c# - Jarvis 算法(礼品包装)或 graham-scan - C#
问题描述
我有一个形状列表,我必须在它们周围制作一个凸包。我试着做一个礼物包装算法(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个,依此类推。显然这没有任何意义。而这
你知道格雷厄姆或贾维斯的任何实现吗?
解决方案
推荐阅读
- python - Python3 Gtk3:D-Bus 库似乎设置不正确;无法读取机器 uuid:无法打开“/etc/machine-id”
- python - 将每天包含多个条目的列表转换为标准白天索引,并为每个条目提供自己的列
- python - 从字典中创建数据框中的分类变量
- r - 将字符日期转换为日期格式
- javascript - 使用节点 JS 向 MongoDB 添加数据,我收到此错误:“TypeError: Cannot read property 'username' of undefined”
- html - 我的按钮内的文本在多行中垂直而不是水平,我如何将它写在一行中?
- tensorflow-federated - TFF:将客户端拆分为训练和测试或将每个客户端数据集拆分为训练和测试之间的区别
- reactjs - 目前没有配置加载器来处理这个文件
- bash - 使用空格分隔的文件名准备字符串并跳过名称已存在于 bash
- python - tensorflow/keras 神经网络中的复杂输入/输出是可能的吗?