相关：Is there a simple algorithm for calculating the maximum inscribed circle into a convex polygon?
我正在写一个图形程序，其目标是艺术而不是数学 . 它使用几何图元（例如线段或小角度的弧）逐步构成图像 . 因此，它寻找开放区域以填充更多细节;随着可用的开放区域变小，细节变得更精细，因此它的分形很松散 .
在给定的步骤中，为了决定接下来要做什么，我们想要找出：哪个是最大的圆形区域仍然没有现有的几何图元？
问题的一些限制
-
不需要准确 . 一个足够接近的答案很好 .
-
不精确应该在保守的方面犯错：一个几乎最大的圆圈是可以接受的，但是一个可以接受的圆圈 .
-
CPU效率是一个优先事项，因为它会经常被调用 .
-
程序将在浏览器中运行，因此内存效率也是一个优先事项 .
-
我必须对细节水平设置一个限制，大概受内存空间的限制 .
-
我们可以跟踪已经以任何所需方式绘制的图元，例如空间索引 . 不需要这些的准确性;例如存储边界框而不是弧线就可以了 . 然而，我们拥有的精度越高越好，因为它将允许程序绘制到更高级别的细节 . 但是，考虑到基元的数量可以随细节水平呈指数增长，我们希望过去细节的存储不会随着基元的数量线性增加 .
总结优先顺序
-
内存效率
-
CPU效率
-
精度
P.S.
我用圈子来描述这个问题，但如果找到最大的清晰黄金矩形（或金色椭圆）更容易，那也会有效 .
P.P.S.
这张图片给出了我想要实现的目标 . 这是卷须绘制程序的开始，其中关于在哪里发芽卷须以及有多大的决定是在不考虑剩余的开放空间的情况下做出的 . 但现在我们想知道，接下来哪里有吸引卷须的空间，有多大？那之后呢？
3 回答
一种非常有效的方法是递归地将您的区域划分为矩形子区域，在必要时将它们分开以将占用区域与未占用区域分开 . 然后你只需要跟踪每次最大的未占用区域 . 请参阅https://en.wikipedia.org/wiki/Quadtree - 但您无需拆分为正方形 .
给定任何矩形，您可以在其中绘制一条线，以使该线两侧的至少一个矩形为黄色矩形 . 因此，您可以递归地在矩形内竖立分区，以便除分区形成的矩形之外的所有矩形都是黄金矩形，并且剩下的添加矩形非常小 . 你可以这样做来创建一个类似四叉树的结构，其中几乎所有留下的矩形都是金色矩形 .
这似乎是一种随机算法可能有用的情况 . 随机选择点数，拒绝并选择更多因为某些原因它们不合适的点数，然后找到您选择的最小距离到已包含的每个数字 . 具有最大分钟的随机点将是您的选择 .
随着图形复杂性的增加，样本点的数量可能不得不增加 .
通过检查附近的良好选择点可以改进随机算法 . 继续检查邻居，直到不再可能改进为止 .
这是一种使用固定内存量和每次更新时间的简单方法，无论您使用多少个绘图基元 . 根据您需要的“分辨率”高度，可以控制需要多少内存（以及每次更新的时间）：
将空间划分为点网格 . 我们将维护一个2D数组d []，它记录从网格点（x，y）到条目d [x，y]中任何已经绘制的基元的最小距离 . 最初，将此数组中的每个元素设置为无穷大（或一些巨大的数字） .
每当绘制一些图元时，迭代所有网格点（x，y），计算从（x，y）到刚刚绘制的图元的最小距离（或对它的一些保守近似） . 例如，如果刚刚绘制的图元是以（p，q）为中心的半径r的圆，那么该距离将是sqrt（（x-p）^ 2（y-q）^ 2）-r . 然后用这个新的距离值if更新d [x，y]它小于其当前值 .
可以绘制最大圆而不触及任何已绘制图元的网格点是距离目前为止绘制的任何图元最远的网格点 . 要找到它，只需扫描d []找到它的最大值，并记下相应的索引（x，y） . d [x，y]将是您可以安全地用于此圆圈的最大半径 .
根据需要重复步骤2和3 .
几点：
对于具有区域的图元，可以将0或负值分配给与图元内的网格点对应的所有d [x，y] .
对于任何凸基元，通常可以通过从刚绘制的基元边界扫描行（或列）"outward"来避免更新大多数d []数组：从当前网格点到基元的距离永远不会减少，因此如果这个距离变得大于d []中的先前最大值，然后我们就知道我们可以停止扫描这一行，因为我们在它上面计算的距离值不可能小于它上的现有距离 .