问题标签 [convex-hull]

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

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

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

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

在这里我画出凸面。

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

我有一组带有 xyz 坐标的 3D 点。我想计算这些点的凸包。我已经完成了可用的算法，但我不能在 Perl 中做到这一点。Perl Math:ConveextHull 模块我也检查过，但我不知道如何将这些 3D 点作为输入。请帮我。

我正在尝试实现 Bowyer-Watson 算法以生成平面中一组点的 Delaunay 三角剖分。该算法假设存在边界超三角形，但也提到了一些替代方案，例如保持点集的凸包。

因此，当我们决定通过在增量算法中假设凸包来产生点的 delaunay 三角剖分时，如果点位于凸包之外，我们应该从该点绘制顶点到凸包上包含面的所有顶点从该点可见的船体。

我想知道我该如何解决这个问题？我是否应该最初生成所有点的凸包，或者像在增量方法中一次添加一个点一样，我是否应该以 DCEL 的形式维护一个凸包？

编辑：在上图中，如果我的点 P 位于平面中一组点的凸包之外，我需要计算从该点可见的包的边缘。[船体的绿色边缘]

我希望这张图片有助于澄清这个问题。

提前致谢

我正在尝试使用凸包制作一个 2D 游戏，用于在离散物理系统中限制体积，但我似乎无法让碰撞响应在他们应该做的任何地方工作。我不知道我的 googlefu 是否缺少或者那里什么都没有，但我找不到任何关于响应的信息（有很多关于生成船体的内容）。有没有人有任何开始这方面的提示？

谢谢。

我写了以下代码

一个 if(waitKey(33)=='q') 中断；img1=img2.clone(); }

}

1.）为什么轮廓没有以红色显示，尽管我通过 CV_RGB(255,0,0) 指定了它。2.)当我取消注释线 convexHull(Mat(cont),hullPoints,false); ，程序显示运行时错误。为什么会发生。谁能告诉我convexHull（）的确切格式及其参数的含义

我有以下代码

如何在这个convexHull..cvConvexityDefects() 中找到凸面缺陷需要const cvArr * 作为参数。但是我有来自convexHull 的向量点类型结果..那么如何键入cast ..？

我正在编写 C（不是C++）代码来在矩形轮廓上运行凸包。（大大简化的）代码如下所示：

Whereimg和contours都是有效的。这些行之间还有很多内容，但其中的 FindContours 部分已经过测试可以正常工作。

此代码引发异常：错误：cvApproxPoly 中的参数错误（不支持的序列类型）。

有人告诉我，问题是没有设置将序列标识为折线的标志，我已经尝试过这个建议hull->flags = hull->flags | 512，但可能这些标志在 2008 年到现在之间的某个时间发生了变化，因为这不起作用。

所以问题是：如何在 cvConvexHull2() 的结果上使用 cvApproxPoly()？我应该使用什么数据类型，cvApproxPoly() 的正确参数是什么？

我需要解决动态凸包算法问题，即维护2D点的凸包，我可以在其中添加和删除点。

天真的方法很明显O(N)；每当N添加/删除其中一个点时，我们都会从头开始重新计算凸包。但是，我负担不起线性时间，所以我正在寻找一种次线性算法。到目前为止，我找到了一堆论文，所有这些论文都描述了一些复杂的算法，这些算法具有疯狂的时间界限，需要很长时间才能实现。即使是最古老的高效算法，由于 Overmars 和 Leeuween，这O(log^2 N)似乎也太复杂了。（像往常一样，此类论文中描述的大多数算法在结构/算法方面与其他参考论文有大量依赖关系）

我正在寻找更简单但不一定新颖的东西，它在最坏的情况下比线性表现更好（例如O(sqrt N)）。最后，我不介意时间是否摊销。有任何想法吗？

（简单来说，我主要是指不需要超过几百行代码的东西。）

我有一个点数组，还有两个点（A 和 B）。最后两个点形成一条线，我试图找出我的数组中的哪些点离这条线最远。我将如何在 Java 中做到这一点？

我想知道这是否是为了找到与 A 和 B 之间的距离，但这在我的脑海中并不好。

附加信息：我认为这是一个线段。鉴于这是 QuickHull，我不知道它是否有所作为。在数学和公式方面，我从来都不是最伟大的，所以更多的解释会更好。谢谢！

有没有一种很好的算法方法来组合多个正方形（每个正方形有四个 x/y 点）来绘制画布中连接图形的轮廓？

我想确保工作的数字如下：

• 两个正方形连接成一个矩形
• 四个正方形连接成一个更大的正方形
• 两个对角线的正方形，就像一个矩形，每端有 45 度的三角形——这可能是最不规则/最特殊的情况......
• 三个或四个正方形连接在一起形成像俄罗斯方块（TM）块“L”块的凹形

有没有一种简单的方法来计算用于从所有正方形点绘制线路径（可能是填充图形）的外部点？

谢谢！

更新：我们想要这样做的原因是因为我们想要显示在 2xn 数组中彼此相邻的同一组的正方形（但在某些情况下也可能是 1xn）。如果我只是遍历不同的方块并以其他方式形成分组，也许会有一个更简单的答案？