问题标签 [convex-hull]

我需要想出一个凸包算法来读取一堆 X ， Y 坐标并勾勒出图像的轮廓。我正在用 python 编码有什么想法吗？

尝试使用 ComputationalGeometry 包中的 PlanarGraphPlot 绘制 ConvexHull，但在图形中使用时不起作用。

关于如何使用 Graphics 绘制 ConvexHull 的任何想法？

我正在使用 OpenCV 2.2，我需要确定凸包的凸面缺陷。我在文档中找不到任何关于凸面缺陷的信息，这让我想知道 OpenCV 2.X 是否仍然支持它，或者它是否被重命名？

无论如何，我尝试使用 C 函数

但是，我无法将我的转换std::vector<Point> hull为CvArr. to的CvArr参数cvConvexityDefects应该是一维和连续的 int 数组，我没有成功创建（尝试强制转换，手动复制到 CvSeq 结构中，...）。

有任何想法吗？

如果您能帮助我解决这个问题，我将不胜感激:)

与OpenCV 2.X / C++ 中的这个问题 cvConvexityDefects 有关吗？， 我也有同样的问题。OpenCV C++ wrapper 没有 C 版本中出现的函数 cvConvexityDefects，所以我尝试编写自己的版本。

部分代码是（请注意countour和hull都是vector<Point>，分别计算：

输出是Convex hull must represented as a sequence of indices or sequence of pointers in function cvConvexityDefects。真的我不知道如何以正确的方式进行转换，我一直在网上搜索并尝试调整/复制/理解一些代码，但它总是使用 C 语法。

我希望我很清楚。先感谢您！

我有一个 3D 表面，作为一组三元组 (x_i, y_i, z_i)，其中 x_i 和 y_i 大致在一个网格上，每个 (x_i, y_i) 都有一个关联的 z_i 值。典型的网格是 20x20

我需要在给定的公差范围内找出哪些点属于曲面的凸包。我正在寻找一种有效的算法来执行计算（我的客户提供了一个 O(n³) 版本，在 400 点数据集上需要大约 10 秒...）

每次我计算一组点的 ConvexHullArea 时，我都会得到以下结果：

输出似乎正确

正常吗？

有没有办法解决这个问题？永久静音？

谢谢

我正在尝试在 VB6 中用 java 实现这个礼物包装算法（yoshihitoyagi！）。我很确定我已经正确地做到了这一点，但由于某种原因，它不起作用。返回的数组只有 1 个元素。我希望有人可以看看（一双新的眼睛），让我知道我是否明显遗漏了什么。

这是我的代码：

我所有的数组都从 1 开始。因此，如果您看到 1 和 0 之间的任何差异，这就是原因。

我知道这很多，但任何帮助将不胜感激。

谢谢！！！！

我目前正在尝试使用 OpenCV 2.3 和 c++ 来检测手（戴着绿色手套），并区分不同的手势。

此时此刻，我的下一步是获取手的特定特征（凸缺陷）。

到目前为止，我已经在我的过程中使用了这些功能：

这些工作非常出色，我已经能够findContours()通过使用drawContours().

下一步，这就是我所在的地方，是 using convexHull()，它也适用于 OpenCV 2.3。然而，我还没有弄清楚矢量结果的convexHull()实际外观（它们包含哪些特征）。

但这就是棘手的部分。

我发现旧版本的 OpenCV（使用 c which uses IplImage）有一个简洁的小函数cvConvexityDefects()，可以在凸包上给出一组缺陷。这些是我需要的，但 OpenCV 2.3 似乎没有这样的功能，我不知道如何使用旧语法来获得这些结果。

这是.Open CV 文档的链接cvConvextDefects。

我要求的是类似的 OpenCV 2.3 函数，或者是用于查找这些缺陷的自写代码或算法。或者一种将旧的 2.1 语法用于矢量结果或类似的方法。

（我知道我可以使用其他特征，矩形边界框和拟合圆。但我确信凸缺陷会产生最可区分的特征。）

解决方案 - 我最终使用了这篇文章中的 c++ 包装器。这个包装器 唯一不起作用的似乎是缺陷向量的韭菜，它应该很容易解决。

下一步是从这些缺陷中获取一些可用数据。（乍一看。数据似乎是convexHull或Contour上的单点或这些的计数。我起初期望一组两个点，或一个点和一个长度，但它似乎不是.如果我用这个打“砖墙”，我会再发一篇文章）

问题已回答，请参阅问题末尾的解决方案。仍然欢迎更多评论/答案。

所以我在将所有元素放入一个内存存储时遇到了一些麻烦，我设法做的最好的事情就是每次都覆盖存储，并且只取出覆盖它的最终元素，遗憾的是这还不够。

我主要是一名 Java 程序员，所以我可能会使用一些 Java 术语来代替 C 等效项，并且在引用 C 对象时可能会提到错误的类型，所以我提前为此申请（并且不要让我开始使用指针）。

最终，我要做的是获取图像中的所有凸面缺陷并将它们存储到一个连续空间中，然后我将通过 JNI 将其传回 Java。商店的类型并不重要，在这个阶段我只需要它工作，如果我们继续进行，我可以进行优化，但我认为堆栈、队列、列表、向量或类似的东西可以完成这项工作。目前我一直在尝试循环添加 CvSeq 对象组到一个大型 CvSeq，我将发布我的代码并在发布后讨论它：

所以我们创建了一个扫描仪，虽然我们可以找到轮廓，但我们这样做并检查它是否大于给定的阈值。假设我们在它周围创建了一个船体，然后找到它和船体之间的缺陷。这意味着缺陷中可以有多个对象，我想在每次循环时将它们添加到allDefects但我可以让它继续下去的唯一方法是使allDefects等于缺陷，这意味着它在每个循环中都会被覆盖。您可以看到一些注释代码，我尝试将其像堆栈一样推送，但这会因错误而崩溃：

断言失败：sizeof(((defects))->first[0]) == sizeof(CvSeqBlock) && ((defects))->elem_size == sizeof(CvSeq)，文件 vtoolsModified.cpp，第 1407 行

按照文档“cvConvexityDefects() 例程返回一系列 CvConvexityDefect 结构”，这是一个充满CvConvexityDefect (s)的CvSeq 。如果有任何帮助，cvConvexityDefects 的签名是：

所以总结一下我要做的是找到一个轮廓，找到它的外壳，找到它们之间的缺陷，将所有这些缺陷添加到一个大型存储中，重复直到没有剩余的轮廓，将带有所有缺陷的大型存储返回给 Java . 这是我正在寻求帮助的粗体字。

任何人都可以帮助或指出可以的来源吗？（我已经在这个特定问题上工作了大约 2 周，所以已经找到了很多资源，是的，我觉得自己真的很愚蠢，因为我没有设法弄清楚什么应该是一个有效的简单循环。）

谢谢

编辑 - 由于评论而添加了更多细节。

编辑 2 - 已回答问题，得到的固定代码如下

看起来我对 C 缺乏了解是根本问题。我假设我需要在应该使用 CvConvexityDefect 的地方使用 CvSeq。修正后的代码如下：

您可以看到我还在检查以确保返回的缺陷少于 100 个（有时会破坏系统的缺陷是数百万个）并确保CV_GET_SEQ_ELEM不返回 null（我不确定它是否可以返回 null，但我会检查以防万一。

我在 OpenCV 2.3.1 中成功实现了轮廓的 Delaunay 三角剖分。

使用 cvPointPolygonTest 我可以得到凸包中的所有三角形，然后我尝试在三角形质心上执行另一个 cvPointPolygonTest 以了解它们是否在主轮廓中，这样我就可以对轮廓进行约束三角剖分。

但是，它不能很好地工作，因为一些三角形（例如，一个走路的人，他的两条腿很远）“越过”一个洞。

有谁知道执行约束三角测量的方法。我想到了convexityDefects，但无法理解如何从这个开始。

提前致谢 ！

本

实际上，这不是凸包缺陷问题，而是三角剖分问题。这张图片会告诉你麻烦：

特别是在三角包的底部，您可以看到三角剖分在轮廓之内和之外，因为 OpenCV 正在对凸包进行三角剖分。我想找到一种方法来对轮廓本身进行三角测量。

我发现了一些关于在轮廓本身中添加 Steiner Points 的想法，但找不到从 OpenCV 开始的地方。

我的想法是：

• 测试三角形是否在轮廓内和外；
• 如果为真：获取交点；
• 并将其添加到 cvSubdiv2D。

我说得对吗？

感谢您的耐心和您的回答！