ios - 将不规则形状拟合成圆形

Question

我有一个带有 alpha channel 的位图，显示出不规则的形状。我尝试缩放和移动形状以适合给定半径的圆。任何想法如何以有效的方式做到这一点？这必须在运行时计算。

精度可以到1..2像素，更重要的是不要切离形状。我想这可以通过逐步调整偏移量和比例值、绘制和检查碰撞来完成，但这听起来有点昂贵。

非常感谢涉及 Swift/iOS 的解决方案......

Answer 1

第一步，扫描图像以找到所有前景像素，并计算它们的凸包(使用 monotone chain 方法，线性时间为 O(N)，因为您可以按排序顺序检测点)。这将大大减少要考虑的点数。

然后你可以找到smallest enclosing circle ，可以在线性时间O(H)内构造。

查找Nayuki's Smallest Enclosing Circle似乎是随机算法的干净实现。