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

我要做的是把这些正方形放在一个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
  

• 从圆形开始 r 0.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不知道我想要比例布局。想象一下,整个作品被压缩成一个方形。)