问题标签 [convex-hull]

我在 Matlab 中使用不同的凸包函数来查找形成凸包的点坐标。但是，这些函数返回三角形矩阵。如何指定这些点？谢谢。塞皮德

我有一些类似于力导向图示例的东西。主要区别在于没有强制力——布局是静态的，除了用户拖动交互。我添加了在用户定义的节点组周围绘制凸包（作为 svg:path 元素）的代码。随着节点的移动（即.on("drag")），计算外壳的代码被触发。这意味着当节点被拖动时它会不断触发。通常有 10 到 30 个船体；一个节点可能在一个或多个外壳中。见下文：

我试图弄清楚是否有更有效（更高性能）的方式来做我正在做的事情。暂时保持高水平：

拖动时，更新所有船体图形：

1. 对于每个船体，创建组成节点坐标的数组。
2. 将上述数组中的每个坐标对替换为与原始点相距一定距离r的 8 个点。这是为了填充/扩张船体，因此它实际上不会接触任何节点。
3. 将计算出的坐标馈送到d3.geom.hull.

我在 Chrome 中获得了大约 50 fps，这一点也不差，但它似乎是一个非常低效的设置。

我唯一明确的想法是将节点包含在节点数组中的船体的 ID 存储在节点数组中，并且只更新那个/那些船体而不是所有船体。我还想知道更有效的数据结构来存储船体数据（而不是路径本身）。目前数据结构如下所示：

请原谅这个开放式问题，但我希望有一些我不熟悉的编程技术在这里可以很好地工作。

convhullMATLAB 中的和convhulln函数实现了哪些算法来计算凸包？

我找不到任何参考..

我有一个计算图像凸包的程序。我正在尝试使用此信息来计算输入图像中存在的手指数量。从一些冲浪中我发现这样做（数手指）的方法是

1. 寻找轮廓
2. 凸包
3. 凸缺陷

但是我在使用凸度缺陷函数时遇到了麻烦。它编译得很好，但在运行时程序会因某些输入图像而崩溃，但不会因其他输入图像而崩溃，我似乎无法弄清楚原因。

这些是输入图像

1. 此图像导致崩溃
2. 但事实并非如此。
3. 即使它与上述类似，这也会导致崩溃

代码..

我正在编写 Quick Hull 算法，其中包括检查一个点是否位于三角形内。为此，我创建了以下两个函数，如果点在内部，则返回 true，否则返回 false。

但是，从某种意义上说，结果是出乎意料的，有些点被正确分类，有些则没有，我无法弄清楚问题所在。有人可以帮我验证我写的代码是否正确。方法是我使用向量来确定一个点是否与三角形每条边的顶点位于同一侧。代码是：

我试图弄清楚在凸包的弯曲点绘制圆圈。使用OpenCV 文档中的示例进行凸包，我有一个凸包。但我不太确定如何在指尖所在的点绘制圆圈，这些点基本上是凸包的弯曲点。

我希望有人能指导我完成这个。

谢谢您的帮助

我正在使用层次聚类来尝试可视化已扁平化为二维的大量数据。我想要做的是创建一个可视化，允许我通过将集群渲染为其组成点的凸包来查看层次结构中不同高度的数据。这个问题最难的部分是我需要一种算法，当我向上移动时，它可以有效地合并对集群的凸包。我已经看到了很多用于在 O(n log n) 时间内计算点的凸包的算法，但在这种情况下，利用问题的子结构似乎会更有效，但我不完全确定如何。

编辑：

有关更多信息，数据结构是一个数组，它从聚类的原始点开始，然后说明哪些点/聚类被组合以形成下一个聚类。所以它有点像树/指针结构，但包含在一个大数组中。重要的部分是，查看任何超级集群的两个组成集群是有效的，但获取属于集群的所有点的集合并不高效。所以任何合理的算法都必须自下而上地工作。

所以假设我们在某个地方的层次结构的中间，并且预先计算的层次结构表明集群 A 和 B 被合并以产生集群 C。我们是从下往上的，所以我们已经计算了簇 A 和 B 中的点，因此我们只需将它们组合起来即可生成簇 C 的凸包。簇 A 的凸包实际上可以是一个点、一对或一个完整的多边形。集群 B 也是如此。因此，有几种情况应该如何合并这些以形成集群 C 的凸包，但我敢打赌，有一个聪明的解决方案可能会将单例和对以与多边形相同的方式处理。

最明显的解决方案是使用集群 A 和 B 的凸包的组合点集来计算凸包。但我需要在 100k 点的层次结构上执行此操作，所以我想知道是否有更有效的组合 A 和 B 的凸包的方法。

编辑2：

好的，所以我尝试用 ASCII 码来说明我的意思。簇A的凸包是1-2-3-4，B的凸包是5-6-7-8，C的凸包是1-2-4-7-8-5。据推测，集群 A 和 B 在它们的外壳内包含额外的点，但这些显然不可能成为 C 外壳的一部分，因此问题在于确定在何处“拼接”集群 A 和 B 的外壳以形成C 的船体，基于点的坐标。这是整个过程的归纳步骤。（最终 C 将与集群 D 组合，依此类推，直到算法以最顶层的集群结束，该集群将所有点的凸包作为其凸包）。

从下面的代码中，我可以绘制出最大的轮廓，其中质心标记为小圆圈，船体标记为黄线。如何绘制凸面缺陷？我应该使用 circle() 函数还是 drawContours() 函数？

上面的代码有效，但是只有一个轮廓可以使用，它是最大的轮廓，所以我认为使用 vector> 作为船体太多了。我该如何简化呢？

下面的代码来自另一个 stackoverflow 问题，但它没有显示如何使用缺陷变量将凸面缺陷绘制到 Mat 图像上。如何做到这一点？

我不想使用 IplImage。我更喜欢马特。

我正在尝试使用一组坐标的外边界构建一个 MKPolygon。

据我所知，没有提供的功能可以实现这一点Xcode（MKPolygon 方法将使用所有点来构建多边形，包括内部点）。

经过一些研究，我发现凸包解决了这个问题。在研究了各种算法之后，我最能想到实现的一种算法是 QuickHull。

这需要外部纬度坐标并在两者之间画一条线。从那里，您根据该线将您的点拆分为两个子集，并处理外部纬度之间的距离以开始构建三角形并消除其中的点，直到您留下外部边界。

我可以通过查看最小/最大纬度来找到外部点，并且可以在两者之间画一条线 ( MKPolyline) - 但是我如何确定一个点是落在这条 MKPolyline 的一侧还是另一侧？

一个后续问题是是否有命中测试来确定点是否属于 MKPolygon。

谢谢！

我想用 d3 围绕一个分组的力有向图构建一个船体。

我已经用圆圈构建了图表。但我现在想用路径（船体）加入圆圈的交叉点。如果不加入交叉点，在这组圆圈周围绘制一个外壳就足够了。我尝试了带有 Convex Hull示例的 Force-Directed Layout。但是我有覆盖文本的文本和圆圈以及连接文本的链接。

您可以在JsFiddle上查看此代码的示例：