寻找在一个区域内最大的空旷圆形的近似算法

Question

相关：是否有一种简单的算法来计算内切于凸多边形的最大圆？

我正在编写一个图形程序，其目标是艺术性而不是数学性。它使用几何基元（如小角度线段或弧）逐步构成图像。随着程序的进行，它寻找开放区域以填充更多细节；随着可用的开放区域变小，细节变得更加精细，因此它松散地呈分形状。

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

问题的一些限制

• 它不需要是精确的。足够接近的答案就可以。
• 不精确应该偏向保守方向：接近最大的圆是可以接受的，但不完全为空的圆是不可接受的。
• CPU效率是优先考虑的，因为它将经常被调用。
• 程序将在浏览器中运行，因此内存效率也是优先考虑的。
• 我将不得不设置一个限制，即详细级别受到内存空间的限制。
• 我们可以以任何所需的方式跟踪已绘制的基元，例如空间索引。这些的精确度不是必需的；例如，存储边界框而不是弧将是可以接受的。但是，鉴于基元数量可以随着详细级别的增加呈指数增长，因此我们希望过去详细信息的存储不会随着基元数量线性增加。

总结优先顺序

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

P.S.

我用圆形来表达这个问题，但是如果更容易找到最大的清晰金色矩形（或椭圆形），那也可以。

P.P.S.

这张图片给出了我想要实现的一些想法。这是一个蔓延式绘图程序的开始，在其中决定了在哪里生长蔓延，以及大小，而无需考虑剩余的开放空间。但现在我们想知道，哪里有空间绘制下一个蔓延，并且大小是多少？然后在哪里？

- LarsH

Answer 1

一种非常有效的方法是将您的区域递归地分成矩形子区域，在需要将占用区域与未占用区域分开时进行拆分。然后，您只需要跟踪每个时间的最大未占用区域即可。请参见https://en.wikipedia.org/wiki/Quadtree - 但您不需要拆分成正方形。

对于任何矩形，您可以在其中绘制一条线，以便线两侧的至少一个矩形是黄金矩形。因此，您可以在矩形内递归地建立分区，以便由分区形成的所有矩形都是黄金矩形，而剩下的一个矩形则非常小。您可以这样做来创建类似四叉树的结构，其中剩下的几乎所有矩形都是黄金矩形。

- mcdowella

Answer 2

这似乎是一种随机算法可能有所帮助的情况。随机选择点，如果由于某些原因不适合，则拒绝并选择更多，然后找到你选择的每个图形与已包含的图形之间的最小距离。最大最小值的随机点将是你的选择。

随着图形复杂度的增加，样本点的数量可能需要增加。

通过检查好的选择附近的点可以改进随机算法。不断检查邻居，直到不可能再进行改进为止。

- Edward Doolittle

---

好的。但是，从每个随机点到已包含的每个图形的最小距离的查找可能会变得非常昂贵，因为已包含的图形数量随着细节级别的增加呈指数级增长。您有没有想过如何使这更易于处理？（顺便说一句，我刚刚在问题中添加了一张图片。） - LarsH

一旦您随机选择了一个中心点，如果您可以确定一个圆是否包含另一个元素，那么您可以通过二分查找找到最大半径。您提供的示例图形很有趣，因为它与边缘相连，所以仅当圆与图形相交时，圆才包含一个元素，这可以通过在绘制圆之前检查圆上的点的颜色来轻松确定。您的程序是否符合这种情况？ - Edward Doolittle

Answer 3

这是一种简单的方法，每次更新都使用固定数量的内存和时间，无论你使用多少绘图原语。需要多少内存（和每次更新的时间）可以根据需要控制，以实现所需的“分辨率”。

1. 将空间分成一个点的网格。我们将维护一个二维数组d []，其中记录了从网格点（x，y）到任何已绘制的基元的最小距离，在条目d [x，y]中。最初，将此数组中的每个元素设置为无穷大（或某个巨大的数字）。
2. 每当您绘制一些基元时，请迭代所有网格点（x，y），计算从（x，y）到刚绘制的基元的最小距离（或其保守近似值）。例如，如果刚刚绘制的基元是半径为r以（p，q）为中心的圆，则该距离将是sqrt（（x-p）^ 2 +（y-q）^ 2）- r。然后，如果新距离值比其当前值小，则使用此新距离值更新d [x，y]。
3. 可以绘制最大圆而不接触任何已绘制基元的网格点是到目前为止任何基元最远的网格点。要找到它，只需扫描d []以找到其最大值，并注意相应的索引（x，y）。 d [x，y]将是您可以安全使用此圆的最大半径。

如有必要，请重复步骤2和3。

几点说明：

• 对于具有面积的基元，您可以将0或负值分配给所有d[x，y]与基元内部的网格点相对应。
• 对于任何凸基元，您通常可以通过从刚绘制的基元边界“向外”扫描行（或列）来避免更新大多数d[]数组：从当前网格点到基元的距离永远不会减小，因此如果这个距离变得大于d[]中先前最大值，则我们知道可以停止扫描该行，因为在其上计算的进一步距离值可能永远不会小于现有距离。

- j_random_hacker

---

我喜欢这个想法，特别是最后一个要点。它让我想起了扩散受限聚集（https://en.wikipedia.org/wiki/Diffusion-limited_aggregation#Artwork_based_on_diffusion-limited_aggregation）。顺便说一下，我刚刚在问题中添加了一张说明性图片。 - LarsH

也许可以通过使用图形本身的最低有效位来减少内存需求。 - Edward Doolittle

@EdwardDoolittle：你能详细说明一下吗？我不明白图形的最低有效位如何被使用。你是指从画布/屏幕读取像素颜色数据吗？ - LarsH

@LarsH：恐怕我没有看到与扩散受限聚集的联系，但这可能是因为我不知道它是如何工作的 :) - j_random_hacker

@LarsH 是的，没错。内存已经被分配来表示图像。颜色数据的最高有效位将对应于图形的可见颜色变化。最低有效位可以用来存储其他信息，例如建议答案中的距离信息。根据颜色分辨率的不同，最低有效位信息可能更或者更少地对肉眼可见。您需要找出颜色分辨率是否足够高，以及信息是否可以快速读取/写入。根据浏览器/系统可能会有所不同。 - Edward Doolittle