问题标签 [grahams-scan]

我必须实现格雷厄姆扫描算法。这是我的代码：

它不适用于排序部分。函数 _arctan2() 和 _sqrt() 返回较大的值。即 sqrt 返回 -1464986461。为什么会发生？结果，点不是按 alfa 排序的，而是以未知的方式排序的。如果我手动设置点的顺序，算法就可以正常工作。

你能告诉我它不工作的方式吗？

我正在研究 Convex hull 和 Graham Scan 来实现它，它引起了我的注意，每个人都使用过堆栈。所以我想问一下为什么算法中精确使用了堆栈，使用堆栈有什么好处？

Jarvis：对于具有 h 个极值点的 n 个输入点，该算法在最坏情况下需要 O(nh) 时间。

Graham：在最坏的情况下为 O(nlogn)。

来源CGAL 的 ref，我使用这两种算法的地方。

这意味着当 h 小于 logn 时，Jarvis 可以更快地处理数据集（比如说二维）。但是我希望看到它的实际效果，但我找不到为此目的的数据集。有人知道吗？

谷歌搜索产生这个链接，它实际上支持我上面所说的。

如何在线性时间内使用格雷厄姆扫描或任何其他算法合并两个纠结的凸包（像这样）以形成凸包？

我有一个坐标列表，应该形成我需要排序的路径的边缘。我正在尝试使用 Grahams 扫描并尝试了以下几个样本：

1. 格拉姆斯扫描仪
2. ConvexHull.cs
3. 凸包算法

这些代码对于我拥有的几个测试用例都失败了，我不确定出了什么问题。

编辑：

这些坐标应该是切线的一部分。如果坐标未排序，则切线会随机发生，而不是随着风暴的进展可能是直的或弯曲的正确路径。

我正在创建形成风暴路径的圆圈的切线。可以在这里看到一个例子：

编辑#02

如果形成切线的点是有序的，那么正确的形状（忽略最后的半圆）应该是这样的。

测试用例：

测试用例#01

测试用例#02

测试用例#03

请指导我一个资源、算法或代码，我可以在其中找到一个可靠的浮点坐标排序算法，并且在这样做时不会消除点。速度不是优先级，准确性是优先级。

我将不胜感激所有投入。谢谢

目前正在与 Convex HUll 一起使用 Graham's Scan。我是一名学生，所以我试图自己完成它，但是我一直在筛选多个站点以找到答案。简而言之，我有我的构造函数，一个来自文件，一个随机生成，可以工作，所以我能够创建一个点数组。下一步是实现快速排序，按极角排序。这是通过比较器类完成的。比较器类是我卡住的地方，我们被告知使用点比较和交叉比较来比较角度，但我很迷茫。

就是这样，在卡住之前，我只是在比较方法上经历了一些小事情。

quickSort 和 partition 方法非常标准，但我将添加它们，以便你们可以广泛了解所有内容：

我知道我基本上需要启动并运行 Compare 类，然后才能启动快速排序方法，但我觉得我什至根本不知道如何使用点/交叉比较，所以我真的很迷茫。

如果有人愿意提供帮助，我将不胜感激！非常感谢您的观看，祝您有个愉快的夜晚。

当我编写这个小凸包可视化器时，我基本上一直遵循wikipedia entry for Graham scan的每一步。它通常按预期工作，但在更高的输入大小下，通常会出现错误点。

ArrayList<Point>该程序首先用给定数量的随机生成的Point对象填充一个。然后它找到Point最低的y。如果多个Point对象共享最低值，则使用具有最低值的对象x。

接下来，它生成ArrayList<Double>每个Point相对于Point上面找到的特定的角度。它对这些角度及其对应的Point对象进行快速排序，以生成一个ArrayList<Point>排序后的值。

下一步是我认为我的问题所在。首先，我复制ArrayList<Point>并调用它edges（请注意，如果我没有使用原件ArrayList<Point>进行可视化，则不需要克隆）对于其中的任何三个有序Point对象，edges我们将调用A,B,和C，如果从AB到BC有一个右转，然后B应从船体中排除并从 中删除edges。AB我通过取叉积的 z 值来确定转弯是右转还是左转（负 z 表示BC右转）。该程序会删除任何导致右转的点并继续前进。

我主要添加changed变量是为了循环多次，以验证是否跳过了某些内容。但是，错误仍然存​​在。有时，它按预期工作。

然而，经常有至少一些不正确的Point对象。

现在我注意到的是，在左转发生之前，有多个Points正确地左转，但仍然是错误的，因为它们最终位于应该是凸包的内部。这可能是回溯的问题吗？我觉得重复循环应该可以捕捉到这些情况。

我正在尝试计算矩形联合的周长，其中我有左下角和右上角的点。每个矩形都位于 x 轴上（每个矩形的左下角是 (x, 0)）。我一直在研究不同的方法，似乎 Sweep-Line 算法是最好的方法。我也看过 Graham Scan。我的目标是 O(n log n) 算法。老实说，虽然我迷失了如何继续，我希望这里的人可以尽最大努力为我简化它并尝试帮助我准确理解如何实现这一点。

我从我所做的研究中收集到的一些东西：

我们需要对这些点进行排序（我不确定我们对它们进行排序的标准）。

我们将分而治之（达到 O (log n)）。

我们需要计算交叉点（最好的方法是什么？）

我们需要某种数据结构来保存这些点（也许是二叉树？）

我最终将在 Java 中实现这个算法。

我应该从文件中读取点并将这些点作为数组接受，以便我可以实现 Grahams Scan，但是我的程序似乎只接受第一行点有人可以帮忙吗？

}

但只接受 1,2

我经历了chan的算法。对我来说似乎并没有好多少。有没有办法可以用其他任何东西替换 graham scan 中的排序部分？这样可以进一步减少 O(nlogn) 时间。Java 实现是首选。