一个圆形可以装多少个正方形？

Question

一个圆形可以装多少个正方形？

algorithmmathlanguage-agnosticgeometrypacking

8

一个半径为 R 的圆形能放多少个尺寸为 a×a 的正方形？

我不需要解决方案，只需要一些开始思考的点子。

- Transcendental

1

方块可以旋转吗？这将会显著复杂化算法。 - Tony

2

编程语言并不重要，因为这更像是一个数学问题。建议前往Math Stack Exchange提问。该问题已被投票关闭。 - Rob Kennedy

仅仅因为他提到语言不重要，并不意味着这一点就一定是离题的。如果楼主只是在寻找可以解释为其所选语言的伪代码，那该怎么办呢？ - ggrigery

1

无论这是否与主题有关，我认为他很可能会在数学堆栈交换网站上获得更好的答案。 - jcoder

1

相关网站：http://www.packomania.com/ - Robᵩ

显示剩余4条评论

4个回答

0

使用类似于中点圆算法的方法对圆进行光栅化。填充像素的数量就是你可以放入圆中的正方形数量。当然，由于你实际上并没有填充像素，只是计算它们，所以这应该花费与圆周长成比例的时间，而不是其面积。

你需要仔细选择光栅化的半径，以便只计算严格在圆内部的像素。

编辑：这可能不完全正确，因为将子像素偏移应用于网格可能会改变结果。我将保留答案，因为它可能为精确解决方案提供有用的起点。

- John Bartholomew

我认为由于问题的对称性，唯一有趣的亚像素情况是每个轴上的“偶数”和“奇数”（圆的中心在正方形中间或正方形边缘），因此您只需要尝试这四种情况。 - Kevin Reid

-1

你可以把任意数量的正方形装进一个圆里。如果你对此怀疑，可以在一张纸上画一个大圆，然后在其中画一个边长为10^(-18)米的正方形，重复这个过程。当你接近圆的边界时，开始画边长为10^(-21)米的正方形。

因此，你的第一步必须是精确地明确你的问题并陈述你的问题。

- High Performance Mark

3

我认为“一些尺寸”是指，给定一个维度D，有多少个边长为D的正方形可以放入某个半径为R的圆中。 - yshavit

3

我认为“高性能马克”非常清楚这一点，只是想逗乐一下。 - Gunther Piez

@drhirsch 嗯，如果把明确表达的问题拿来假装成没有问题，那就太愚蠢了。 - yshavit

我的编辑之前，它的措辞不是很清晰，但意图是明确的。 - Gunther Piez

对于圆内的非对齐正方形，请参考 http://www2.stetson.edu/~efriedma/squincir/（尤其是 28＆34）。 - greybeard

-1

经过几分钟的思考，只是一个尝试...

如果你只用半圆并在最后将其加倍。我会从一个正方形网格开始，其长度为直径，宽度为半径，基本上覆盖半圆。然后检查每个正方形的4个角落，并确保它们的坐标位于圆的半径内。当然，这需要您在某种坐标系统或网格上绘制圆和正方形。

我希望这有意义... 它在我的脑海中，似乎有点难以表达 :)

编辑：画出来后，我认为稍加调整这种方法就可以奏效。我会沿着直径排列正方形，但将第一个向下滑动直到它合适为止。把它放在那里，开始在旁边排列正方形，直到它们不再合适。走到这一行正方形的边缘，重复同样的步骤，直到你的正方形行到达半径。

- ggrigery

3

如果答案要求正方形存在于直径上（例如，正方形的平分线是直径），而不是沿着直径延伸，那怎么办？这个解决方案没有考虑到这一点。 - kylex

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Matt Esch · Accepted Answer

很抱歉回答这么长。我的方法是先确定一个理论最大值和一个保证最小值。在解决问题时，你可以使用这些值来确定你所使用的任何算法的好坏程度。如果你能想到一个更好的最小值，那么你可以使用它代替。

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

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。基本上，你用一个装满的正方形占据了略大于25%的内部正方形，这意味着你得到了约20%的近似覆盖率。