一个半径为R的圆可以装多少个 a × a 的正方形？
我不需要解决方案。我只需要某种开始的想法。
问问题
15677 次
4 回答
5
我很抱歉写了这么长的答案。我的方法是从理论上的最大值和保证的最小值开始。当您处理问题时，您可以使用这些值来确定您使用的任何算法的好坏。如果你能想到一个更好的最小值，那么你可以使用它来代替。
我们可以通过简单地使用圆的面积来定义问题的上限
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 的答案，那么你不能在圆圈内放置任何正方形。
现在有了理论最大值和绝对最小值，您可以开始尝试任何类型的启发式算法来打包正方形。一个简单的算法是将圆圈分成几行，并在每一行中放置尽可能多的正方形。然后，您可以将此最小值作为指导，以确保您提出更好的解决方案。如果您想花费更多的处理能力来寻找更好的解决方案，您可以使用理论值作为您与理论最佳值的接近程度的指导。
如果你关心这一点，你可以计算出我确定的最小算法覆盖的最大和最小理论百分比给你。最大的正方形总是覆盖一个固定的比率（我认为 pi/4 或大约 78.5% 的圆的内部面积）。所以最大的理论最小值是 78.5% 的覆盖率。最小非平凡（即非零）理论最小值是当您只能在最大正方形内放置 1 个正方形时，当您要打包的正方形比最大正方形的宽度和高度的一半大 1 时，就会发生这种情况。适合圈子。基本上你用 1 个方格占据了超过 25% 的内方格，这意味着你得到了大约 20% 的覆盖率
于 2012-03-04T01:07:07.553 回答
0
使用类似中点圆算法的方法对圆进行光栅化。填充像素的数量是您可以在圆圈中容纳的正方形数量。当然，由于您实际上并没有填充像素，只是计算它们，这应该花费与圆的周长成比例的时间，而不是它的面积。
您必须仔细选择光栅化的半径，以便只计算严格在圆内的像素。
编辑：这可能不完全正确，因为将子像素偏移应用于网格可能会改变结果。我将在此处留下答案，因为它可能为精确解决方案提供有用的起点。
于 2012-03-02T17:35:53.770 回答
-1
您可以将任意数量的正方形打包成一个圆圈。如果你怀疑这个说法，在一张纸上画一个大圆圈，然后在里面画一个边长为 10^(-18)m 的正方形，重复。当你接近圆的边界时，开始画边长为 10^(-21)m 的正方形。
因此，您的第一步必须是细化您的问题并更准确地陈述您的问题。
于 2012-03-02T17:06:17.660 回答
-1
经过几分钟的思考，只是在黑暗中开枪......
如果您使用一半的圆圈并在最后将其翻倍怎么办。我将从直径长度和半径宽度的正方形网格开始，基本上覆盖了半圆。然后检查每个正方形的所有 4 个角，并确保它们的坐标在圆的半径内。这当然需要您在某种坐标系或网格上绘制圆形和正方形。
我希望这是有道理的......它在我的脑海中，似乎有点难以表达:)
编辑：画出来后，我认为这种方法可以稍作调整。我会沿着直径排列正方形，但将第一个向下滑动直到它适合。将那个放在适当的位置并开始在它旁边排列正方形，直到它们不再适合为止。移到这条正方形线的边缘并重复相同的步骤，直到您的正方形行达到半径。
于 2012-03-02T17:12:37.607 回答