将正方形定位在最小直径的圆上

Question

给定n个边长为l的正方形,如何确定圆的最小半径r,以便我可以沿着圆周均匀分布所有正方形而不重叠？(约束:第一个方格将始终位于12点.)

后续问题:如何放置n个高度为h和宽度为w的相同矩形？

例如http://pub.n3rd.org/circle.png

Answer 1

可能有一种数学上聪明的方法来做到这一点,但我不知道.我觉得有点复杂,因为每个不同数量的正方形的几何形状都不同; 4它是一个菱形,5它是五边形,依此类推.

我要做的是将这些正方形放在1个单位的圆上(太小,我知道,忍受我)在它上面均匀分布.这很容易,只需将你的360度对等(划分)为正方形.然后测试你所有的方块与他们的邻居重叠; 如果它们重叠,则增加半径.

通过使用智能算法来接近正确的大小,您可以使此过程不那么愚蠢.我正在考虑像牛顿算法这样的东西:给定两个连续的猜测,其中一个太小而一个太大,你的下一个猜测需要是这两个的平均值.

您可以迭代到您喜欢的任何精度.每当猜测之间的距离小于某个任意小的误差范围时停止.

编辑我有一个更好的解决方案:

如果你问"我怎么知道方块是否重叠？"我正在考虑告诉你什么.这让我对如何精确计算圆周大小有了一个想法:

将你的方块放在一个太小的圆圈上.您知道如何:计算360/n角与其相交的圆上的点,并将正方形的中心放在那里.实际上,您还不需要放置方块,接下来的步骤只需要中点.

计算方形与其邻域的最小距离:计算X的差异和中点的Y差异,并取最小值.X和Y实际上只是圆圈上的余弦和正弦.

你会想要与其邻居相比最小的任何方格(顺时针,比方说).因此,您需要绕着圆圈工作才能找到最小的圆圈.

方块之间的最小(X或Y)距离需要变为1.0.因此,只需取最小距离的倒数并乘以圆的大小即可.Presto,你的圈子大小合适.

编辑

在不失一般性的情况下,我认为可以将我的解决方案略微下调,以便接近编码.这是一个改进:

• 假设正方形的大小为1,即每个边的长度为1个单位.最后,你的盒子肯定会大于1个像素,但这只是一个缩放问题.

• 摆脱角落案件:

  if (n < 2) throw new IllegalArgumentException();
  if (n == 2) return 0.5; // 2 squares will fit exactly on a circle of radius 0.5
  

• 从圆圈大小r0.5 开始,对于任意数量的正方形> 2,这肯定会太小.

  r = 0.5;
  dmin = 1.0; // start assuming minimum distance is fine
  a = 2 * PI / n;
  for (p1 = 0.0; p1 <= PI; p1+=a) { // starting with angle 0, try all points till halfway around
     // (yeah, we're starting east, not north. doesn't matter)
     p2 = p1 + a; // next point on the circle 
     dx = abs(r * cos(p2) - r * cos(p1))
     dy = abs(r * sin(p2) - r * sin(p1))
     dmin = min(dmin, dx, dy)
  }
  
  r = r / dmin;
  

编辑

我把它变成了真正的Java代码,并得到了与此类似的东西来运行.代码和结果在这里:http://ideone.com/r9aiu

我使用GnuPlot创建了图形输出.通过将输出中的点集剪切并粘贴到数据文件然后运行,我能够创建简单的圆形框图

plot '5.dat' with boxxyerrorbars

该.5的文件中起到尺寸的箱子......懒,但工作的解决方案..5适用于中心的两侧,因此盒子的大小正好是1.0.

唉,我的算法不起作用.它使得半径太大,因此将盒子放置得比必要的远得多.即使按比例缩小2倍(在某些地方使用0.5可能是一个错误)并没有帮助.

对不起,我放弃了.也许我的方法可以被挽救,但它不会像我那样工作.:(

编辑

我讨厌放弃.当我想到一种方法来挽救我的算法时,我正要离开我的电脑:

该算法将X或Y距离中较小的一个调整为至少为1.很容易证明这只是愚蠢的.当你有很多盒子然后在圆圈的东边和西边时,你的盒子几乎直接堆叠在一起,它们的X彼此非常接近,但是它们之间只有足够的Y距离可以保存它们.他们.

所以...为了使这项工作,您必须将dx和dy 的最大值(至少在所有情况下)至少缩放半径(或者它是半径的两倍？).

更正的代码在这里:http ://ideone.com/EQ03g http://ideone.com/VRyyo

再次在GnuPlot中测试,它产生漂亮的小圆盒,有时只有1或2个盒子正在接触.问题解决了!:)

(这些图像比它们高很宽,因为GnuPlot不知道我想要比例布局.想象一下整个作品挤成方形:))