问题标签 [convex-hull]

标准凸包算法不适用于（经度、纬度）点，因为标准算法假定您需要一组笛卡尔点的包。纬度-经度点不是笛卡尔坐标，因为经度在反子午线（+/- 180 度）处“环绕”。即，经度179以东2度为-179。

因此，如果您的点集恰好跨越了反子午线，您将错误地计算出环绕世界的虚假船体。

关于我可以使用标准凸包算法来纠正这个问题的技巧的任何建议，或者指向正确的“地球”船体算法的指针？

现在我想起来了，除了跨越反经线之外，还有更多有趣的案例需要考虑。考虑一个环绕地球的点“带”——它的凸包没有东/西边界。或者更进一步，{(0,0), (0, 90), (0, -90), (90, 0), (-90, 0), (180, 0)} 的凸包是什么？——它似乎包含了地球的整个表面，那么它的周边有哪些点？

原帖：

我正在尝试找到凸多边形的最外层顶点（与多边形外的点P相关）。现在，我只关心矩形（但是，我想要一种适用于任何凸多边形的算法）。

我的计划是构建一条从外部点P到中心点C的线。根据这条参考线，我将构建从点P到点1、2、3和4的线。由于点2和4将与参考线具有最大（最正）和最小（最负）的角度，因此它们将被标识为最外面的顶点。

这是最适合这项工作的算法吗？如何从参考角度计算角度（最好在 Java 中）？

更新澄清：

我已经画了线（红色的参考线）。如您所见，从P到2的线在参考线的一侧创建最大的角度，而从P到4的线在另一侧创建最大的角度。因此，这些是最外层的顶点。

当输入中的所有点都位于凸包上时，如何避免快速壳算法的性能不佳？

因此，我正在学习 Convex Hull 算法，并编写从幼稚的 Bruteforce 到 Graham Scan 的所有算法。

这是我的蛮力 O(n^4) 算法。一开始，假设所有点都是船体的一部分。对于每个可能的三角形，消除位于三角形内的所有点。最后，那些没有被淘汰的点将成为船体的一部分。

这是 Java 代码（已修复：使用 Thomash 的解决方案）

我试着在视觉上看到这些点，它们似乎是正确的，但是我不知道如何建立点的顺序来绘制凸包多边形？任何帮助表示赞赏。

Open-CV 2.4 Android-Java：

我搜索了这样的轮廓（MatofPoint 列表）：

然后是凸包（必须是 MatofInt 的列表）

凸包想要一个 MatofInt，但 drawcontours 想要一个 MatofPoint.. 那么该怎么办呢？

提前谢谢..

编辑：@OpenCV4Android

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

根据我的程序，凸包是

但是，我希望凸包是

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

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

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

我正在阅读格雷厄姆扫描算法以从 CLRS 中找到凸包。CLRS 中针对 Convex hull 给出的算法是::

我无法理解这一行（算法的第 2 步）：

如果两个或多个点相对于 p0 具有相同的极角，那么除了最远的点之外，其他所有点都是 p0 和最远点的凸组合，因此我们完全不考虑它们。

1. 这是什么意思？如果多个点相对于 Po 有相同的极角怎么办？

也可以说，我做了一个结构

2. 我应该如何使用 C++ STL 库实现排序步骤？我的意思是，我应该如何定义比较器功能sort(P+1, P+N, comparator)？

我正在使用 OpenCv 来检测指尖，但现在遇到了一些障碍！findContours & convexHull & convexityDefects 方法不适用于我的项目。这是我第一次提出问题。谢谢大家！

我的代码如下：

这是我的手图：

http://www.billwang.net/bbs/oldattach/2006/12/29/billwang_5315954-038-embed.jpg

我已经根据这里的教程编写了这个，但我无法获得图像的凸包（我使用的是类似教程中所示的手形图像）。我得到源和边缘输出很好，但应该绘制轮廓和凸包线的“绘图”输出没有显示任何绘制，而是完全黑色。关于为什么会这样的任何想法？

*最大是我在图像中的最大轮廓

但是convexityDefects给了我这个错误“断言失败（hull.checkVector（1，CV_32S）> 2）”。有人请帮助我，我不想求助于使用 C 解决方案。

已编辑

vector<vector<int>>在将类型传递给凸度缺陷之前，我尝试使用该类型进行创建，但凸度缺陷仍然给我错误“断言失败（ptnum > 3）..”。