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

Question

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

algorithmmathgeometry

18

给定边长为l的n个正方形，如何确定最小半径r，以便我可以将所有正方形均匀分布在圆的周长上，而不重叠？（约束条件：第一个正方形始终位于12点钟位置。）

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

_{（来源：n3rd.org）}

- n3rd

这是什么背景？这是作业吗？ - Will Dean

8

@Oded - 这绝对不是一个MathOverflow的问题 - 在我看来，这在这里完全合法，因为它不是作业（即使是作业，只要标记正确，也是合法的）。 - Will Dean

1

@Oded - 嗯，这可能是正确的，但这显然不足以使它成为MathOverflow问题。 - Will Dean

1

@Oded - 我和威尔的观点一致，而且我认为最佳答案（卡尔的）是一种迭代解决方案，是一个算法，而不仅仅是一个公式的支持。 - Nick Fortescue

2

该问题要求一种算法，这意味着它是针对某种程序的。因此，它肯定有编程元素。 - IVlad

显示剩余12条评论

6个回答

4

我会计算最小半径的上限，通过使用外接正方形而非正方形本身来完成。

我的计算结果为：

Rmin <= X / （sqrt（2）* sin（180/N））

其中： X是正方形边长，N是所需正方形数量。

我假设圆被放置在其圆周上的位置。

- 编辑 -

根据下面评论中Dave的想法，我们也可以计算一个不错的下限，即将圆视为内嵌在正方形中（因此半径为X/2）。这个下限为：

Rmin >= X / (2 * sin (180/N))

- Eyal Schneider

利用这个上限，为什么不尝试使用二分查找来寻找最小的半径，使得没有矩形相交呢？时间复杂度为O(n * log Rmin)。 - Dave O.

@Dave 跟进：我们可以通过使用位于矩形内部而不是包含它们的圆来获得下限。现在使用二分查找找到介于Rmin和Rmax之间的正确半径 -> O(n * log(Rmax-Rmin)) - Dave O.

@Dave：好主意，尤其是考虑到两个边界。请忽略我上次的评论。 - Eyal Schneider

2

嘿，看到有人评论说n3rd正在组合一个（径向）菜单后，我开始思考使用圆形来显示菜单项比正方形更好看（《无冬之夜》有没有？），这也与此相当契合。 - JAB

1

如已经注意到的那样，在圆周上等距放置n个点的问题是微不足道的。问题（不是非常）困难的部分是要找出需要的圆的半径，以给出一个令人愉悦的正方形布局。我建议您遵循其他答案之一，并将正方形放在足够大的圆形“缓冲区”内，以容纳正方形并满足您的美学要求。然后检查相邻正方形中心之间弦长的公式。现在，您已经知道了圆心处由正方形中心之间的弦所夹的角度，并且可以轻松地通过三角函数计算圆的半径。

至于您的后续问题：我建议您先在圆上解决正方形边长为min(h,w)的问题，然后将正方形转换为矩形，将圆形转换为离心率为h/w（或w/h）的椭圆。

- High Performance Mark

0

你从任意一个圆开始（例如，直径为(* n l)），并将正方形均匀地放置在圆周上。然后你遍历每一对相邻的正方形，并执行以下操作：

计算连接它们中点的直线，

计算该直线与介入的正方形边缘的交点（M1和M2是中点，S1和S2是相应的正方形边缘交点：

                S2         S1
M1--------------*----------*---------------M2

------------------------
|                      |
|                      |
|                      |
|                      |
|          M1          |
|           \          |
|            \         |
|      -------*------- +--------
|      |       \       |       |
|      |        \      |       |
-------+---------*------       |
       |          \            |
       |           M2          |
       |                       |
       |                       |
       |                       |
       |                       |
       -------------------------

计算比例因子，以使S1和S2重合（简单地将M1-S1和S2-M2之和除以M1-M2的比率），并

最后将圆按找到的比例因子的最大值进行缩放。

编辑： 这是确切的解决方案。然而，稍加思考可以进一步优化速度：

您只需要对最接近45°的正方形进行此操作（如果n为偶数）或45°和135°（如果n为奇数；实际上，您可能会证明只有其中一个是必要的）。
对于较大的n，圆上正方形的最佳间距将迅速接近正方形对角线的长度。因此，您可以预先计算几个小n（多达十几个），然后使用对角线得出足够好的近似值。

- Svante

不，我认为这并不是最优解决方案。你要求的是四个角刚好接触的比例尺。我发现这会使圆形太大了；只需要水平或垂直的一组边缘接触即可。 - Carl Smotricz

不，我没有写也不是指那些角落。我是在写关于相邻两个正方形中心连线与正方形边缘交汇处的情况。 - Svante

@Carl Smotricz：我添加了一个草图。 - Svante

@Svante 从我的角度来看，您忽略了一个问题，即在缩小圆的半径时，矩形之间的相对位置也会发生变化，因此会使 S2 和 S1 的值失效。 - Dave O.

当缩小时，相对位置不会改变。想一想：连接中点的线的角度仅取决于n，即正方形的数量。 - Svante

我想我被纠正了。感谢您的图表，这看起来可能会很有效。 - Carl Smotricz

0

我会这样解决它：

为了找到半径r和长度l之间的关系，让我们分析无量纲表示法

- 在圆上获取中心点(x1,y1)..(xn,yn) - 从每个中心点获取第i个正方形的右下角和第i+1个正方形的左上角 - 这两个点应该具有相等的x或y，以产生较小的l - 对于每个中心点都应重复该过程，并且产生最小l的那个是最终解决方案。

这是最佳解决方案，可以通过调整xLR[i]和yUL[i+1]的公式来适应矩形。

将尝试提供一些伪代码。

编辑：
程序中存在一个错误，相邻正方形/矩形的右下角和左上角不一定是最近的点。

- Unreason

0

假设您已经解决了3或4个正方形的问题。

如果您有n >= 5个正方形，并将一个正方形放在圆的顶部，那么另一个正方形将掉落到与您的圆同心的笛卡尔平面的第一象限。

问题是找到一个半径r的圆，使得靠近顶部的圆的左侧和顶部圆的右侧不会“交叉”。

顶部圆的右侧的x坐标为x1 = L/2，其中L是正方形的边长。靠近顶部的圆的左侧的x坐标为x2 = r cos a - L/2，其中r是半径，a是每对正方形中心之间的角度（a = 360 / n度）。

因此，我们需要解决x1 <= x2，这导致

r >= L / cos a.

L 和 a 已知，因此我们完成了 :-)

- Mau

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

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

- Carl Smotricz · Accepted Answer

可能有一种数学上聪明的方法来做到这一点，但我不知道。我认为这有点复杂，因为每个不同数量的正方形的几何形状都不同；对于4个正方形，它是一个菱形，对于5个正方形，它是一个五边形，等等。

我会将这些正方形放在一个1单位圆上（太小了，我知道，但请忍耐）。这很容易，只需将360度分成正方形的数量。然后只需检查所有正方形是否与其邻居重叠；如果它们重叠，则增加半径。

您可以使用智能算法使此过程比听起来要聪明得多。我正在考虑类似于牛顿算法的东西：给定两个连续的猜测，其中一个太小，另一个太大，您的下一个猜测需要是这两个的平均值。

您可以迭代到任何精度。当猜测之间的距离小于某个任意小的误差边缘时停止。

编辑我有更好的解决方案：

我在思考如果你问“我如何知道正方形是否重叠？” 这给了我一个想法，如何在一步中精确计算圆的大小：

将您的正方形放在一个太小的圆上。你知道怎么做：计算你的360 / n角度相交的圆上的点，并把正方形的中心放在那里。实际上，你还不需要放置正方形，下一步只需要中点。

计算正方形与相邻正方形之间的最小距离：计算中点的X差异和Y差异，并取其中的最小值。实际上，X和Y只是圆上的余弦和正弦。

您将希望最小化任何正方形与其相邻正方形（顺时针）之间的距离。因此，您需要绕着圆圈工作，找到最小的一个。

正方形之间的最小（X或Y）距离需要变为1.0。因此，只需取最小距离的倒数并将圆的大小乘以它即可。 Presto，您的圆的大小就正确了。

编辑

我认为可以在不失一般性的情况下将我的解决方案明确到接近编程。以下是一个改进：

Assume the squares have size 1, i.e. each side has a length of 1 unit. In the end, your boxes will surely be larger than 1 pixel but it's just a matter of scaling.

Get rid of the corner cases:

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

Start with a circle size r of 0.5, which will surely be too small for any number of squares > 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不知道我想要等比例布局。只需想象整个作品被挤成一个正方形的形状即可 :)