用户绘制圆形的凸包

Question

我正在开发一个游戏，需要找到一组点的凸包。我正在尝试选择正确的算法。这些点集是用户绘制的形状，所以它们有一定的顺序。理想情况下，用户会画一个椭圆，但只要是单笔画都可以。以下是一些示例：

我想找到这些形状的凸包。我找到的所有凸包算法都假定一组随机、无序的点。在我的情况下，用户通过点击和拖动鼠标绘制点，因此这些点是有序的。那么哪种算法最适合我，以便找到这些点的凸包呢？

注：

特别地，许多算法是输出敏感的。当n是所有点集中的点数时，原始的h是凸包中的点数。对于这些形状，我预计h~=n，因为它们本质上就是轮廓。

最后，整个目标是找到这些点的面积最小的矩形，例如：

除了先找到凸包之外，还有更好的方法来寻找矩形吗？经过研究，这似乎是最好的方法，但我的特殊情况可能不同。

提前感谢您！

- retrovius

Answer 1

请远离O（NLog H）算法，它们复杂且速度慢！

使用O（NLog N）的算法是更好的选择。我推荐使用单调链方法，既容易又快速。

您不必担心复杂度顺序O（NLog N），这只是由于排序阶段导致的。额外的Log N / Log H因子并不是那么灾难性的（对于凸点集不存在），而排序的渐近常数非常好。

如果您想追求最大效率，则您的点的特定排列建议使用另一种方法：点将形成长的递增（递减）序列，您可以轻松检测并通过合并步骤进行排序。复杂度将降至O（NLog K），其中K是单调序列的数量，因此几乎为O（N）（这称为自然归并排序）。

您离Melkman的O（N）算法的用例不远了，该算法可用于简单多边形的外壳。不幸的是，在曲线关闭时，简单条件可能会失败，我看不到简单的修复方法。

---

对于边框矩形，旋转卡壳算法绝对是您的好帮手。

- user1196549

---

谢谢，这正是我所需要的！关于曲线的结束，我计划通过检查用户是否在接近起点处结束线条，并轻松调整曲线以适当连接来解决。我将测试您的解决方案，并在有任何问题时与您联系。 - retrovius

Answer 2

要找到沿特定方向对齐的最小包围矩形，您需要知道该方向和正交方向上的极点，并且凸包以一种特别方便的方式编码了这些信息，例如旋转卡尺。如果您愿意进行近似，可以尝试每隔五度（或其他）尝试方向，运行时间为O(nd)，其中d是方向数。如果您有SIMD支持，则此方法效果很好。

- David Eisenstat

---

所以你的意思是这些算法已经很适合我的需求了？另外，SIMD代表什么？谢谢！ - retrovius

Answer 3

我在想，如果你采用以下方法会发生什么：

将多边形视为2 x N矩阵

P = [x1, x2, ..., xN;
     y1, y2, ..., yN]; 

其中每列包含多边形顶点的x和y坐标。然后，对于任何角度phi，例如0到pi/2之间的角度，定义旋转矩阵

U(phi) = [cos(phi) -sin(phi);
          sin(phi)  cos(phi)];

接下来，通过矩阵相乘将多边形旋转到角度phi。

P_phi = U(phi)*P;

然后这个函数

f(phi) = ( max( P_phi[1][] ) - min( P_phi[1][] ) )*( max( P_phi[2][] ) - min( P_phi[2][] ) )

矩形的面积是围绕旋转多边形P(phi)的水平和垂直边缘所超出的区域。这里，P_phi[1][]是矩阵P_phi的x坐标的第一行，P_phi[2][]是y坐标的第二行。 因此，您需要找到角度phi和顶点，收集在2 x 4矩阵R_phi中，该矩阵给出了函数f(phi)的最小值，其中phi in [0, pi/2]，因为这是围绕您的多边形的最小面积矩形的面积。找到phi和R_phi后，只需按如下方式旋转回来：R = U(-phi)*R_phi，这就是您要寻找的矩形。

我不确定这个建议是否可行...

- Futurologist

---

这是与David Eisenstat提供的解决方案相同的解决方案。要获得精确的解决方案，您应该尝试由凸包边缘暗示的所有方向，但这相当低效（O（N²））。可以使用适度的d获得近似解，但很容易被旋转卡尺（实际上是旋转方法的增量版本）击败。 - user1196549