问题标签 [convex-hull]

我有大量顶点，其中一些是边，一些是多余的（在形状内部），我想删除它们。

我能想到的最简单的算法是一一检查它们是否碰到了其他人形成的形状。但它应该是一个非常慢的算法。

我考虑过从边缘选择一个（每个示例离原点最远的一个）并计算从这个开始的最长路径......应该得到边缘路径，对吗？

有什么建议吗？

我需要为类分配制作一个 2D 凸包函数，并且我想要一个比分配提供的更强大的测试用例。有没有人知道解决方案的大型测试用例（25 < n < 100）？

假设我在飞机上有大约 1000 个奇点。

然后，我认为可以做的是丢弃不以任何方式影响圆半径的点-凸包不通过的点[使用几种算法之一]。这给我们留下了重要的观点。

现在从这里开始，可以做些什么来找到最小半径的圆？

一旦我了解了如何为圆完成此操作，我希望将其推广到椭圆。

任何指向某些“公共源代码”的链接都会有所帮助，以便我可以将其修改为省略号。

我有一组点。我想将它们分成 2 个不同的集合。为此，我选择两个点（a和b）并在它们之间画一条假想线。现在我想把这条线左边的所有点放在一组里，把这条线右边的点放在另一组里。

我如何判断任何给定点z是在左侧还是右侧？我试图计算azb之间的角度——小于 180 的角度在右侧，大于 180 的角度在左侧——但由于 ArcCos 的定义，计算出的角度总是小于 180°。是否有计算大于 180° 的角度的公式（或任何其他选择右侧或左侧的公式）？

我想要一种算法来计算 4 个 2D 点的凸包。我已经查看了通用问题的算法，但我想知道是否有 4 点的简单解决方案。

我正在尝试制作一张地图，用户可以在其中勾勒出他们想要的任何形状。但是我遇到了一个问题，用户可以选择使多边形的线交叉并排除我想包括的区域的点。

要查看我在说什么，请转到此页面并执行以下步骤：

1. 单击 4 个点以制作方框的 4 个角
2. 在您刚刚制作的 4 个点之间单击以进一步定义框的周长
3. 点击完成

您应该看到如下内容：

有没有一种简单的方法可以解决这个问题，或者我基本上是在处理“旅行推销员”类型的情况？所有的逻辑都是用 javascript 完成的，所以如果你想看看我是怎么做的，请随意“查看源代码”。

我想生成一个二进制掩码，其中所有体素都为一个，而体积外的所有体素为零。体积由一组 3D 坐标（<100；一些坐标在体积内）周围的凸包定义。

我可以使用CONVHULLN获得凸包，但是如何将其转换为二进制掩码？

如果没有通过凸包的好方法，您还有其他想法如何创建二进制掩码吗？

给定平面上的 n 个点。No 3 是共线的。

给定数字 k。

找到 k 点的子集，使得 k 点的凸包在 k 点子集的任何凸包中具有最小周长。

我可以想到一个天真的方法在 O(n^kk log k) 中运行。（找到每个大小为 k 的子集的凸包并输出最小值）。

我认为这是一个 NP 问题，但我找不到任何适合归约的东西。

有人对这个问题有想法吗？

一个例子，

结果：

由于该集合包含 3 个点，因此结果的凸包和周长小于任何其他 3 个点的集合。

我知道有一个最坏情况 O(n log n) 算法可以找到复杂多边形的凸包，还有一个最坏情况 O(n) 算法可以找到简单多边形的凸包。是否存在用于查找复杂多边形的凸包的最坏情况 O(n) 算法？

复杂多边形是线段可能相交的多边形。找到一个复杂多边形的凸包相当于找到一个无序列点列表的凸包。

嗨，我知道盲凸包有 o(n^4) 但我从未见过它的代码！有没有网站有它的代码？谢谢