c# - 用户绘制圆的凸包

Question

我正在开发一款游戏，我必须在其中找到一组点的凸包。我正在尝试选择正确的算法。点集是用户绘制的形状，因此它们是有顺序的。理想情况下，用户画一个椭圆，但只要是单笔画，他们就可以画任何东西。下面是一些示例:

我想找到这些形状的凸包。我发现的所有凸包算法都假设一组随机、无序的点。当用户通过单击并拖动鼠标绘制点时，哪种算法最适合我的特定情况，因此点是有序的。

注意事项:

特别是，许多是输出敏感算法。 O(n log h) 其中n是所有点集合中的点数，原始的，h是凸包中的点集合。对于这些形状，我希望 h ~= n，因为它们本身基本上就是轮廓。

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

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

提前致谢!

Answer 1

远离 O(N Log H) 算法。他们又难又慢!

使用 O(N Log N) 个是一个更好的选择。我推荐 monotone chain方法，既简单又快速。

您不必担心 O(N Log N) 的复杂度，这只是排序阶段造成的。额外的 Log N/Log H 因子并不是那么灾难性的(并且对于凸点集来说是不存在的)，而排序的渐近常数非常好。

如果您追求最大效率，您的点的特定排列建议采用另一种方法:这些点将形成长的递增(递减)序列，您可以通过合并步骤轻松检测和排序。复杂度将降至 O(N Log K)，其中 K 是单调序列的数量，因此实际上是 O(N)(这称为自然归并排序)。

您距离 Melkman 的 O(N) 算法的用例不远，该算法可用于简单多边形的外壳。不幸的是，简单条件可能会在曲线闭合附近失效，我看不到解决该问题的简单方法。

---

对于边界矩形，旋转卡尺绝对是您最好的 friend 。