algorithm - 寻求近似算法以找到区域中最大的清晰圆圈

Question

相关:Is there a simple algorithm for calculating the maximum inscribed circle into a convex polygon?

我正在编写一个图形程序，其目标是艺术而非数学。它利用线段或小角度圆弧等几何基元，一步步合成一幅图。随着它的进行，它会寻找空旷的区域来填充更多的细节；随着可用的开放区域变小，细节变得更精细，所以它是松散的分形。

在给定的步骤中，为了决定下一步做什么，我们想要找出:仍然没有现有几何图元的最大圆形区域在哪里？

问题的一些约束

• 它不需要很精确。一个足够接近的答案就可以了。
• 在保守方面，不精确应该是错误的:几乎最大的圆是可以接受的，但不是很空的圆是 Not Acceptable 。
• CPU 效率是重中之重，因为它会被经常调用。
• 该程序将在浏览器中运行，因此内存效率也是一个优先事项。
• 我必须对详细程度设置限制，大概受内存空间限制。
• 我们可以以任何需要的方式跟踪已经绘制的图元，例如一个空间索引。不需要这些的准确性；例如存储边界框而不是弧就可以了。然而，我们拥有的精度越高越好，因为它将允许程序绘制到更高级别的细节。但是，考虑到基元的数量可以随着细节级别呈指数增长，我们希望过去细节的存储而不是随着基元的数量线性增长。

总结优先顺序

1. 内存效率
2. CPU 效率
3. 精度

附言

我用圆来构思这个问题，但如果更容易找到最大的清晰金色矩形(或金色椭圆)，那也行。

附言

这张图片让我对我想要实现的目标有了一些了解。这是一个卷须绘图程序的开始，在这个程序中，关于在哪里发芽卷须以及有多大的决定是在不考虑剩余开放空间的情况下做出的。但现在我们想知道，接下来哪里有空间画卷须，有多大？那之后呢？

Answer 1

一种非常有效的方法是递归地将您的区域划分为矩形子区域，并在必要时拆分它们以将占用区域与未占用区域分开。然后你只需要每次都记录最大的未占用区域。参见 https://en.wikipedia.org/wiki/Quadtree - 但你不需要分成正方形。

给定任何矩形，您可以在其中画一条线，使得线两侧的至少一个矩形是黄金矩形。因此，您可以递归地在一个矩形内竖立分区，这样除了一个由分区形成的矩形外，其他所有矩形都是黄金矩形，而剩下的添加矩形则小得几乎消失。您可以这样做来创建类似四叉树的结构，其中几乎所有剩下的矩形都是黄金矩形。