问题标签 [grahams-scan]

问题

用户最多可以按任意顺序提供四个经纬度坐标。他们使用谷歌地图这样做。使用 Google 的PolygonAPI (v3)，他们选择的坐标应该突出显示四个坐标之间的选定区域。

问题

如何按（逆）顺时针顺序对一组经纬度坐标进行排序？

解决方案和搜索

StackOverflow 问题

• 绘制可调整大小（不相交）的多边形
• 如何对谷歌地图多边形中的点进行排序以使线不交叉？
• 按顺时针顺序排列四个点

相关网站

• http://www.daftlogic.com/projects-google-maps-area-calculator-tool.htm
• http://en.literateprograms.org/Quickhull_%28Javascript%29
• http://www.geocodezip.com/map-markers_ConvexHull_Polygon.asp
• http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm

已知算法

• 格雷厄姆扫描（太复杂）
• Jarvis March 算法（处理 N 个点）
• 递归凸包（移除一个点）

代码

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

谢谢你。

我几乎完成了 Real World Haskell 的第 3 章。最后一个练习阻止了我。我的代码在运行时会崩溃。有谁可以告诉我代码中的哪一部分有问题？谢谢。

问题：使用前面三个练习中的代码，为一组 2D 点的凸包实现 Graham 扫描算法。您可以在 Wikipedia 上找到关于什么是凸包以及 Graham 扫描算法应该如何工作的详细描述。

回答：

所以我需要使用格雷厄姆扫描算法制作一个凸包，但我有问题，我得到了这个有点凸：

在这里我添加凸点的随机点

在这里，我找到了开始的第一个和最低点。

在这里，我对所有剩余的点进行排序。

在这里我画出凸面。

有人可以告诉我我做错了什么吗？

我写了一个格雷厄姆扫描凸包算法的实现，对于测试数据，我使用了这些点

根据我的程序，凸包是

但是，我希望凸包是

我也用https://github.com/shadwstalkr/GrahamScanDemo/尝试了我的一组点，这也给出了相同的解决方案。经过多次抱怨和抱怨后，我在维基百科上读到“如果对象内的每一对点，连接它们的直线段上的每个点也在对象内，则该对象是凸的。”

在画出我的观点和船体之后。看来我的程序在该定义内生成了一个对象，但这是否意味着仅按角度排序就会给出一个凸包，而在包中没有任何点？

我是否不了解凸包实际上是什么并且我正在解决一个不同的问题，或者我的实现和 shadwstalkr 都不正确？

我正在使用格雷厄姆扫描算法来查找点集的凸包我试图通过它们的极角对点进行排序，但我不知道该怎么做（我已经通过它们对点集进行了排序Y 坐标）。

我已经写的是这样的：

Coord我有 X 和 Y 坐标的类在哪里double。

我还查看了 Stack Overflow 中的一篇类似帖子，其中有人试图用 C++ 实现这个角度，但我不明白qsqrt。我们在 Java 中有类似的东西吗？

如果有人可以帮助我，我会很高兴。

我的代码使用格雷厄姆算法找到凸包效果很好（它向我展示了它应该显示的多边形）但我可以看到它向我发送了一个额外的共线点（尽管我正在处理我的代码中的共线点) 这是我的代码：

我非常等待有一些提示来帮助我找到我的问题

我的格雷厄姆扫描代码不起作用，它应该得到凸包的周长。它得到n个点的输入，可以有小数。该算法返回一个高于实际周长的值。

我正在使用我所理解的： http ://en.wikipedia.org/wiki/Graham_scan

点结构，具有使它与具有最低 y 和 x 坐标的点之间的角度的函数

z叉积函数

距离发生器

获得积分

排序并启动 Graham 扫描

格雷厄姆扫描

获取周长的长度

我有一张带积分的表格。我想根据这些点创建多边形，然后只返回周长上的这些点（不包括多边形内的点）。有没有使用 SDO GEOMETRY 在数据库级别执行此操作的简单方法？我发现某事像 GrahamScan，但我找不到像 Spatial 这样的东西

我正在尝试从 Wikipedia 伪代码实现 Graham Scan，并且在将内容转换为 C# 时遇到了一些麻烦。也许你不介意看看？

这是我所拥有的：

它正在使用这个类：

代码喜欢爆炸，主要是因为我已经阅读了十几个完全不同的伪实现，没有一个能充分解释事情。我遇到了数组的越界错误，我什至不确定应该是坐标，还是坐标 + 1，还是坐标 - 1，或者坐标 + killme -> 最初是“N”或“N” +1'，但正如你所看到的，我正在慢慢失去对这个翻译的想法。

我正在编写一个程序来使用格雷厄姆扫描计算凸包的周长，并且需要在一组数据点中找到最低的 y 坐标。我在 struct 中使用std::min_element(vector.begin(), vector.end())了重载运算符。问题是某些点可能共享相同的最低 y 坐标，在这种情况下，我需要使用它们的 x 值来比较它们。是否有任何快速作弊来检查是否有任何其他点与 min_element 共享相同的 y 而不必遍历所有内容？<point

结构：

函数调用：