问题标签 [grahams-scan]

在我的代码中，我获得了存储在名为matrix. 这些点没有排序，所以我必须对它们进行排序。由于我不知道轮廓是否形成凸包，我必须修改 Graham 扫描。我决定使用以下程序。首先，我使用格雷厄姆扫描到凸包。我保存在一个新向量中的包。然后我从向量中删除凸包的点matrix。然后我必须只对新向量中的剩余点进行排序，为此我将使用距离和点积。

为此，我启动了 Graham 扫描程序。我把自己定位在这个链接上。

所以这是我到目前为止所拥有的：

所以在函数中GeneratPath我想对点进行排序。为此，我将调用 GrahamScan 函数，它传递两个向量和 。matrix我首先使用 搜索具有最低 y 值的点。接下来我必须对点进行排序。因此我使用 C++ 提供的排序功能。作为参数，我使用函数。我找到的原始函数如下所示：chullGrahamScanset_p0compare_angle

由于我的模板中的函数是基于结构的，因此我不得不为我的目的重写该函数。但是，如果我现在发送程序，我会收到错误消息：表达式：向量迭代器 + 偏移超出范围。

我看不到我在哪里犯了错误，但不幸的是。有人可以在这里帮助我吗？

我是 javascript 新手，正在使用 google maps API for javascript。

这是学校的任务，我们获得了一个工作脚本和一些 php 代码来显示地图、获取位置、更新位置等。

我们的任务是实现一个凸包算法。

这些是我遇到的问题：

• 一些对象的数据结构
• 计算完船体线后如何在地图上显示它们

这是代码；

我的主要看起来像这样；

基本上我首先想知道的是为什么 var final_list 有一个结构 [Object, Object, Object, Object, Object] （控制台输出的内容）

因为我收到此错误： Uncaught TypeError: Cannot read property 'length' of undefined at DrawHull

我认为我以正确的方式实现了该算法，但我无法对其进行测试。

如果您需要更多信息，请不要犹豫，也欢迎提出如何使这个问题变得更好的提示[这是我的第一个问题！因此，请考虑到这一点，并在提供建设性反馈的同时保持友善]

我已经实现了 Graham 扫描，但我发现我的程序的瓶颈是排序（80% 的时间）。我想改进它，现在我正在做以下事情：

这给了我确切的角度，但它并不便宜，因为我的角度函数如下所示：

在 Length 函数中，我必须做一个平方根，这是最昂贵的操作之一。但这样我得到了一个很好的订购。

我尝试按 Slope、dot、ccw 对数组进行排序，甚至只从比较中删除 sqrt，但这些都没有为我提供相同的排序。你能给我什么建议吗？

根据 Cormen 的“算法简介”中对格雷厄姆扫描算法的描述，我发现了以下注释：

通过检查非左转，而不仅仅是右转，该测试排除了在所得凸包的顶点处出现直角的可能性。我们不需要直角，因为凸多边形的任何顶点都不可能是多边形其他顶点的凸组合。

有人可以解释一下，为什么我们应该在结果凸包的顶点跳过直角？目前尚不清楚为什么

凸多边形的任何顶点都不能是多边形其他顶点的凸组合

如上所述，我正在尝试实现 Graham Scan Convex Hull 算法，但我遇到了堆栈附加太多顶点的问题。这些点是从此处的 .dat 文件中读取的

对于阅读点，我的功能如下：

我的格雷厄姆扫描如下：

当我使用将前 50 行作为输入的数据集运行它时，它会生成堆栈：

但它应该产生（按此顺序）：

有任何想法吗？

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

所以我试图找到最小的角度。我的逻辑是，角度越小，这个角度的 cos 就越小

但是这段代码以先添加3个圆圈结束，然后再添加1个，依此类推。显然这没有任何意义。而这

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

我正在尝试为 Java 中的凸包实现Graham 扫描算法，并且无法通过相对于 y 值最低的点按极角对点进行排序。

我找到了这个答案并了解如何计算极角，但不了解如何对点进行排序。

我已经看到Collections.sort()正在使用实现，但它们似乎都不能与我想使用的 Point2D 类一起使用，因为我希望能够将双打作为坐标。

基本上，我希望能够ArrayList<Point2D>按它们的极角对同一个 ArrayList 中 y 值最低的点进行排序。

有人可以帮我吗？谢谢。

我正在阅读 Real World Haskell，尝试使用 ghc online解决Ch3、Q10问题。

到目前为止，我有以下代码：

尝试编译此代码时收到以下错误（仅发布部分，多次弹出相同的错误）：

我将不胜感激有关如何修复我的代码的建议或有关从三点确定主要方向的更简洁解决方案的建议。

我正在尝试实现格雷厄姆扫描，我想做这样的事情：

其中点 r 是最底点。但是，我正在努力在 c++ 中实现同样的想法，因为我只能传入比较的函数，我不知道它如何访问最低点。

我知道格雷厄姆扫描的最坏情况运行时间是 O(nlogn) 但我不确定如何生成最坏情况数据。据我了解，这发生在对点进行排序的步骤中，这是否意味着我应该为我使用的排序算法生成最坏的情况数据？

任何帮助，将不胜感激。