用最少量的固定半径圆圈完全覆盖矩形

我已经有这个问题几年了。早在我的城市举行信息学竞赛。我没有解决它，我的老师没有解决它。我没有遇到任何能够解决问题的人。我认识的人知道要给出答案的正确方法，所以我决定把它张贴在这里：用最少量的固定半径圆圈完全覆盖矩形

泽问题

给出一个矩形，X的Y，找到圆的最小量N之间的固定给定半径R，这是完全覆盖矩形的每个部分所必需的。

我想过解决这个问题的方法，但是我什么都没有确定。如果每个圆定义一个内部矩形，则R^2 = Wi^2 + Hi^2，其中Wi和Hi是每个圆所覆盖的实际区域的宽度和高度i。起初我以为我应该让Wi等于Wj任何i = j，H相同。这样，我可以通过使宽高比与主矩形相等来简化问题（Wi/Hi = X/Y）。那样，N=X/Wi。但是，如果X大大超过Y，则该解决方案肯定是错误的，反之亦然。
第二个想法是对于任何给定的i，Wi = Hi。这样，正方形可以最有效地填充空间。但是，如果仍然存在非常窄的条带，则最好使用矩形填充它，或者更好 - 在此之前也使用最后一行的矩形。
然后我意识到没有任何想法是最佳的，因为我总是可以找到更好的方法来做到这一点。它总是接近决赛，但不是最终决赛。

编辑
在一些情况下（大矩形）接合六边形似乎比接合正方形更好的解决方案。

更多编辑
下面是2种方法的比较：三叶草与六角形。对于大型表面，六角形显然更好。然而，我认为当矩形足够小时，矩形方法可能更有效。这是一种预感。现在，在图片中，您会看到左侧14圈，右侧13圈。虽然表面差异比一圈大得多（双倍）。这是因为它们在左侧重叠较少，因此浪费较少的表面。 Hexagonal vs clover

的问题仍然存在：

是正六边形图案本身最佳的？或者应在主矩形的某些部分进行某些调整。
有没有理由不使用常规形状作为“最终解决方案”？
这个问题甚至有答案吗？ :)

来源

2011-10-10 AlexanderMP

这看起来更像数学而不是编程。 –

我会建议在数学上问.S http://math.stackexchange.com/ – yoozer8

如果它不是一个可以解决它的公式，但是一个复杂的算法？我只会重播它。 – AlexanderMP

-2

当圆形作为三叶草放置，四叶中间有第五个圆圈时，圆圈将覆盖等于R * 2 * R的区域。在这种安排中，问题变为：覆盖面积为R * 2 * R的多少个圆圈将覆盖W * H的面积？或N * R * 2 * R = W * H。所以N = W * H/R * 2 * R。

来源

2011-10-10 18:08:40 npclaudiu

你能画吗？根据你的描述（中间有一个圆圈的4个相切圆圈），每3个新增圆圈的边缘表面等于'4 * R^2'（这意味着一个圆圈的边缘表面等于4/3 * R^2';而当使用单个圆圈的正方形给出'2 * R^2'的边缘表面，或者三叶草是一个不太理想的解决方案，或者我没有得到您的想法 – AlexanderMP

对于与R相比较大的X和Y，六角形（蜂窝）图案接近最佳。 X方向圆心的距离为sqrt(3)*R。 Y方向上的行之间的距离为3*R/2，因此您需要大约X*Y/R^2 * 2*/(3*sqrt(3))圈。

如果使用方形图案，水平距离较大（2*R），但垂直距离要小得多（所以你需要大约X*Y/R^2 * 1/2圈。由于2/(3*sqrt(3) < 1/2，六角形模式是更好的选择。

请注意，这只是一个近似值。通常可以稍微摆动常规图案以使标准图案不适合的地方适合。

六角形图案是整架飞机的最佳覆盖：如果X和Y相比R.

在您的具体问题而言都很小，这一点尤其如此。在X和Y有限的情况下，我认为通常可以获得更好的结果。微不足道的例子是当高度小于半径时。在这种情况下，您可以将一行中的圆圈进一步分开，直到每对圆的交点之间的距离等于Y.
具有常规模式会对解决方案施加额外的限制，因此最佳解决方案根据这些限制，在取消这些限制的情况下可能并不理想一般来说，有些不规则的模式可能会更好（参见mbeckish链接的页面）。
同一页面上的例子都是特定的解决方案。多圈的解决方案在某种程度上类似于六边形模式。尽管如此，似乎还没有一个封闭的解决方案。

来源

2011-10-10 21:20:05

This网站从稍微不同的角度攻击问题：给定n个单位圆，什么是他们可以覆盖最大的广场？如您所见，随着圆圈数量的变化，覆盖模式也会发生变化。

对于您的问题，我相信这意味着：不同的矩形尺寸和圆圈大小将决定不同的最佳覆盖模式。

来源

2011-10-10 22:15:51 mbeckish

......难怪我没有'当我还是个孩子的时候想出了一个解决方案，并将它呈现给我 – AlexanderMP

不错！实际上，很容易发现在这个链接上讨论的问题比这个问题严格得多（将这个问题限制在正方形。注意到所需圆的数量随着平方的大小单调递增，因此，给定这个问题的一个算法，你可以在正方形大小上进行二进制搜索，找到最大的正方形 - 以任意的精度 - 由n个圆圈包围） – Nemo

@Nemo - 这只会工作你知道n个圈子中最大的方形圈。不幸的是，我不认为是这样。对于我链接到的页面上显示的12个案例，似乎每个案例都是分开解决的。 – mbeckish

六角形比钻石好。考虑每个覆盖的单位圆的面积比例：

#!/usr/bin/env ruby 

include Math 

def diamond 
    # The distance from the center to a corner is the radius. 
    # On a unit circle, that is 1. 
    radius = 1 

    # The edge of the nested diamond is the hypotenuse of a 
    # right triangle whose legs are both radii. 
    edge = sqrt(radius ** 2 + radius ** 2) 

    # The area of the diamond is the square of the edge 
    edge ** 2 
end 

def hexagon 
    # The hexagon is composed of 6 equilateral triangles. 
    # Since the inner edges go from the center to a hexagon 
    # corner, their length is the radius (1). 
    radius = 1 

    # The base and height of an equilateral triangle whose 
    # edge is 'radius'. 
    base = radius 
    height = sin(PI/3) * radius 

    # The area of said triangle 
    triangle_area = 0.5 * base * height 

    # The area of the hexagon is 6 such triangles 
    triangle_area * 6 
end 

def circle 
    radius = 1 
    PI * radius ** 2 
end 

puts "diamond == #{sprintf "%2.2f", (100 * diamond/circle)}%" 
puts "hexagon == #{sprintf "%2.2f", (100 * hexagon/circle)}%"

而且

$ ./geometrons.rb 
diamond == 63.66% 
hexagon == 82.70%

此外，正六边形的最高顶点的多边形形成一个regular tessellation of the plane。

来源

2011-10-10 23:26:58 phs

根据我的计算是正确的答案是：

D=2*R; X >= 2*D, Y >= 2*D, 
N = ceil(X/D) + ceil(Y/D) + 2*ceil(X/D)*ceil(Y/D)

在特定情况下，如果为X/d和Y/d等于0，则

N = (X + Y + X*Y/R)/D 

Case 1: R = 1, X = 2, Y = 2, then N = 4 

Case 2: R = 1, X = 4, Y = 6, then N = 17 

Case 3: R = 1, X = 5, Y = 7, then N = 31

其余希望它帮助。

来源

2015-11-23 13:37:11 lefsha

你的计算只有在你能证明它们的时候才会有帮助。 – Teepeemm

用最少量的固定半径圆圈完全覆盖矩形

回答

相关问题