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

Question

给定n个边长为l的正方形，如何确定圆的最小半径r，以便可以沿圆的周长均匀分布所有正方形，而不重叠？（约束条件：第一个正方形将始终位于12点。）
接下来的问题是：我怎样才能放置高度h和宽度w相同的矩形呢？

（来源：n3rd.org）

Answer 1

也许有一种数学上聪明的方法可以做到这一点，但我不知道。
我认为它有点复杂，因为每一个不同数量的正方形的几何结构都是不同的；4个是菱形，5个是五角大楼等等。
我要做的是把这些正方形放在一个1个单位的圆上（我知道，太小了，忍受我），均匀分布在圆上。这很简单，只需将360度除以正方形的数目。然后测试你所有的方块是否与它们的邻居重叠；如果它们重叠，增加半径。
通过使用智能算法来接近正确的大小，可以使此过程不像听起来那么愚蠢。我在想类似牛顿算法的东西：假设连续两次猜测，其中一次太小，一次太大，你的下一次猜测需要这两次的平均值。
你可以迭代到任何你喜欢的精度。每当猜测之间的距离小于某个任意的小误差时停止。
编辑我有更好的解决方案：
我在想如果你问“我怎么知道正方形是否重叠？”这给了我一个想法，如何准确计算圆的大小，在一个步骤：
把正方形放在一个太小的圆圈上。你知道怎么做：计算360/N角度与圆相交的圆上的点，然后把正方形的中心放在那里。实际上，您还不需要放置正方形，接下来的步骤只需要中点。
计算一个正方形到它的邻居的最小距离：计算x的差和中点y的差，取其中的最小值。x和y实际上只是圆上的余弦和正弦。
你会想要相对于它的邻居的任何正方形的最小值（比如说顺时针方向）。所以你需要绕着这个圆努力找到最小的一个。
正方形之间的最小（x或y）距离需要变为1.0。所以取最小距离的倒数，再乘以圆的大小。普雷斯托，你的圆圈大小合适。
编辑
在不丧失通用性的前提下，我认为有可能将我的解决方案稍微简化一点，使之接近于编码。这里有一个改进：
假设正方形的大小为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

从0.5的圆圈大小 r开始，对于任何大于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用于调整框的大小…懒惰但有效的解决方案。0.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不知道我想要的是比例布局，所以这些图像比它们的高度要宽。想象一下整件作品被挤成一个正方形：））