Tra*_*tal 6 language-agnostic algorithm math geometry packing
一个大小为a × a的正方形可以装入半径为R的圆中？
我不需要解决方案.我只是需要某种创意.
我为写这么长的答案而道歉.我的方法是从理论最大值和保证最小值开始.当您解决问题时,您可以使用这些值来确定您使用的算法有多好.如果您能想到更好的最小值,那么您可以使用它.
我们可以通过简单地使用圆的面积来定义问题的上限
Upper Limit = floor( (PI * (r pow 2)) / (L * L) )
其中L是您正在打包的方块的宽度或高度,r是您将方块打包成的圆的半径.我们确信这是一个上限,因为a)我们必须有一个离散数量的盒子和b)我们不能占用比圆形区域更多的空间.(一个正式的证明可以在假定我们有一个比这个更多的盒子的某个地方工作,那么盒子的面积之和将大于圆的面积).
因此,有了上限,我们现在可以采用任何存在的解决方案并将其称为最小解决方案.
所以,让我们考虑一下所有圆圈都存在的解决方案,看一看我们可以放在圆圈内的最大正方形.
可以适合的圆圈内的最大的广场对perimiter 4分,并具有一个宽度和长度sqrt(2) * radius(通过使用毕达哥拉斯定理,并使用用于短边的长度的半径)
所以我们首先要注意的是,如果sqrt(2) * radius小于正方形的尺寸,那么你就不能在圆圈中放置任何正方形,因为毕竟这是你能够适合的最大正方形.
现在我们可以做一个简单的计算,使用你指定的L将这个大正方形划分为一个规则的正方形网格,这将给我们至少一个问题的解决方案.所以你在这个最大正方形内有一个sqaures网格.可以放入此网格的一行的方块数
floor((sqrt(2) * radius)/ L)
所以这个最小的解决方案断言你至少可以拥有
Lower Limit = floor((sqrt(2) * radius)/ L) pow 2
圆内的正方形数.
所以,如果你迷路了,我所做的就是把最大的正方形放在圆圈内,然后将尽可能多的正方形包装成一个规则的网格,给我至少一个解决方案.
如果你在这个阶段得到0的答案,那么你就无法在圆圈内放置任何方格.
现在拥有理论最大值和绝对最小值,您可以开始尝试任何类型的启发式算法来打包方块.一个简单的算法就是将圆圈分成几行,并尽可能多地适应每行.然后,您可以将此最小值作为指导,以确保您提供更好的解决方案.如果您希望花费更多的处理能力来寻找更好的解决方案,那么您可以使用理论作为指导,了解您与理论最佳的接近程度.
如果您关心这一点,您可以计算出我所识别的最小算法所涵盖的最大和最小理论百分比.最大的方块总是覆盖固定的比率(pi/4或我认为的圆圈内部区域的约78.5%).因此最大理论最小值为78.5%.最小的非平凡(即非零)理论最小值是当你只能在最大的正方形内放置1个正方形时,当你正在打包的正方形比最大正方形的宽度和高度的一半大时,会发生这种情况.适合圈子.基本上你占据了内部正方形的25%以上,包含1个包装正方形,这意味着你得到大约20%的近似覆盖率