问有多少个正方形可以围成一个圆圈？

EN

我为写了这么长的答复而道歉。我的方法是从理论上的最大值和保证的最小值开始。当您处理这个问题时，您可以使用这些值来确定您使用的任何算法有多好。如果你能想到一个更好的最小值，那么你可以用它代替。

我们可以简单地用圆的面积来定义问题的上限。

Upper Limit = floor( (PI * (r pow 2)) / (L * L) )

其中L是你所包装的正方形的宽度或高度，r是你把正方形填入的圆圈的半径。我们确信这是一个上限，因为( a)我们必须有一个离散的盒子数和( b)我们不能占用比圆的面积更大的空间。(一个正式的证明在某种程度上是可行的，假设我们有一个比这个更多的盒子，那么盒子的面积之和将大于圆圈的面积)。

因此，有了一个上限，我们现在可以取任何存在于所有圆上的解，并称之为最小解。

那么，让我们来考虑一个存在于所有圆中的解，看看我们可以容纳在圆内的最大的正方形。

在圆周上你能适应的最大的正方形有4个点，宽度和长度为sqrt(2) * radius (用毕达哥拉斯定理和半径来表示短边的长度)。

所以我们首先要注意的是，如果sqrt(2) * radius小于你的正方形的维数，那么你就不能在圆圈中拟合任何一个正方形，因为毕竟这是你能拟合的最大的正方形。

现在我们可以做一个简单的计算，用你指定的L将这个大的正方形划分成一个规则的正方形网格，这至少会给我们一个问题的解决方案。在这个最大的正方形内有一个方格。这个网格的一行可以容纳的方格数是

floor((sqrt(2) * radius)/ L)

所以这个最小的解决方案表明你至少可以

Lower Limit = floor((sqrt(2) * radius)/ L) pow 2

圆圈内的方格数。

所以如果你迷路了，我所做的就是把最大的正方形放进圆圈里，然后把尽可能多的方块装进里面的规则网格里，至少给我一个解决方案。

如果你在这个阶段得到一个0的答案，那么你就不能在圆圈内放任何正方形。

现在，有了一个理论上的最大值和一个绝对的最小值，你就可以开始尝试任何一种你喜欢的填充方块的启发式算法。一种简单的算法是将圆圈分成几行，并尽可能多地将每一行的面积进行匹配。然后，您可以将这个最小值作为指导原则，以确保您找到了一个更好的解决方案。如果您想要花费更多的处理能力来寻找更好的解决方案，则可以使用理论指导原则来指导您如何接近理论上最好的解决方案。

如果你关心这个，你可以算出我所确认的最小算法的最大和最小理论百分比。最大的正方形总是覆盖一个固定的比率(π/4，约占圆圈内部面积的78.5% )。因此，最大理论最小值为78.5%。和最低限度的非琐碎(如。非零)理论上的最小值是当你只能在最大的方格内放一个正方形时，当你所包装的正方形大于你在圆圈中所能容纳的最大正方形的一半的宽度和高度的时候。基本上，你只占内方格的25%多一点，只有1块正方形，这意味着你得到了大约20%的盖子。

使用类似于中点圆算法的东西绘制圆圈。填好的像素数是你可以在圆圈中放进的方格数。当然，因为你没有实际填充像素，只是计算它们，这应该需要时间成正比的圆周，而不是它的面积。

你必须小心地选择半径，以便你只计算严格在圆内的像素。

编辑:这可能不完全正确，因为在网格上应用亚像素偏移可能会改变结果。我将把答案留在这里，因为它可能为精确的解决方案提供一个有用的起点。

你可以把任意数量的方块打包成一个圆圈。如果你怀疑这个说法，在一张纸上画一个大圆圈，然后画一个边长10^(-18)米的正方形，重复。当你接近圆的边界时，开始画边长为10^(-21)米的正方形。

因此，你的第一步必须是完善你的问题，并更准确地陈述你的问题。