问题标签 [convex-hull]

Suppose I have an array of points in random order, and I need to find a polygon (by sorting them, such that every adjacent pair represents a side) which passes through all of the points, and its sides are non-intersecting of course.

I tried to do it by selecting a point, and adding all points to the final array which are below it, sorted left to right. Then, adding all points which are above it, sorted right to left.

I've been told that I can add an additional point and sort naturally to avoid self-intersections.. I am unable to figure out that though. What's a simple way to do this?

比赛中问了一个问题。我已经用动态编程及其复杂性解决了这个问题O(n^2)。但我正在寻找更有效的方法。我已经看到动态编程可以使用凸包进行优化。你有什么建议吗。谢谢指教。

我在这里看到了关于在椭圆中包围点的讨论，但是有没有一种算法可以将一组椭圆包围成一个椭圆？焦点可以用来逼近闭合集合的椭圆吗？

是否有一种算法可以找到彼此之间具有一定距离的所有点？还是所有接触的矩形？

我将平面（在纬度/经度坐标系中，具有一定的限制）划分为 nxn 的样本矩形，每个矩形得到一个从 0 到 7 的值。我需要能够为每个值显示岛屿。n > 100 - 可能是 15000。

我写了一些非常蛮力的代码，但我只设法得到了一些非常粗糙的矩形......

我的输入示例：

以上，使用矩形中的点定义（每个 1 和 2 以及其他是我通过一些采样获得的矩形......） - 我最终有几千个 - 可能是十万个小矩形，我想得到每种区域。

我发现我可以使用凸包算法获得区域 - 如果我可以正确地将矩形（或它们的中心点）分成区域。

在我的函数的输入中，我只会得到具有相同度量的矩形。

例子：

我想找到一些算法，这样我就可以在单独的集合中获得正在接触的矩形，或者彼此相距一定距离的点（它们具有绝对坐标），这样我就可以在结果集。

由于矩形是通过采样创建的，因此它们的宽度/高度相同。

有这样的事吗？

我的代码在 VB.NET 中，但 C# 或任何语言或伪代码都会有所帮助。

非常感谢你。

编辑：

我有各种各样的测试，比如

其中 distance_lat 和 distance_lon 是 dim_lat/10，分别是 dim_lon/10

如何从点集合开始计算凸包？

我正在寻找 C# 中凸包算法的实现

我正在尝试使用 scipy (0.10.1) 进行快速破解以可视化凸包。

我可以使用以下代码获得凸包：

结果数组如下所示：

数字是顶点索引。我的问题是它们没有被订购。我需要它们按 CW 或 CCW 顺序排列，以便在 KML 中轻松可视化它们。

有没有简单的方法让 scipy.spatial 计算正确的顺时针顺序？

证明如果每个点的每个坐标都是 p/q 形式的有理数，并且 p 和 q 的值有界，则可以在O(n)时间内计算平面中n个点的凸包。

注意：这是一个家庭作业问题。我可以通过某种方式避免扫描所有点来考虑使用 Jarvis March。也许这可以通过向固定方向（使用有理条件）投射光线来检查下一个点存在的位置来完成。

我正在使用BackgroundsubtractorMOG()基本上提取一个蒙版来分离出前景。然后我convexHull()在面具上使用来定位移动物体的位置。

但我收到以下错误：

我检查了没有。元素以及类型转换的掩码矩阵。但错误仍然存​​在。有没有人遇到过类似的问题。我正在使用 OpenCV 2.4.2

我使用了convexHull 算法来找到一些……不规则形状的轮廓。虽然还不够好...

很可能是因为我不能保证我的形状是凸的......

我有一组矩形，我希望能够获得轮廓外部的所有点 - 但不要抛出任何轮廓点。

凸包算法效果很好 - 但它就像右边的例子一样，所以我丢失了一些关于轮廓的信息。

我想要更接近左边版本的东西，保留外角，只消除里面的点......

有这样的算法吗？

或者，有没有办法将这样的形状（多边形）分解成凸形，以便凸包算法可以正确处理它？

从一个链接到另一个链接，我一直在试图弄清楚如何设置某种算法，比如 Hertel-Mehlhorn 算法——但我不知道在这种情况下使用相交线会做什么......

谢谢你的任何建议。

我找到了这种基于图像矩计算伸长率的方法

如何计算凸壳的伸长率？

其中 'unicocnt' 是通过查找轮廓获取的轮廓。