用等半径的圆覆盖任意区域 [英] Covering an arbitrary area with circles of equal radius

问题描述

算法如何工作，覆盖任意半径相等的圆形区域？

圆的半径以及区域的大小和形状是任意给定的。该区域应尽可能少地覆盖。这些圆圈可能会重叠。

有没有一种算法可以处理这个问题？

解决方案

希望我已经理解你的问题了......

可以证明球体的六边形密堆积（HCP）覆盖了最大体积。因此，我认为用圈子做HCP也会覆盖使用圆圈的最大面积。使用三角形镶嵌您的区域，并在三角形的每个顶点放置一个圆心，其半径为三角形边长的一半。请参阅此以了解我正在谈论的算法的图像。

注意：这与紧密包装在单元格中的原子。

编辑：我以前的方法覆盖了尽可能多的区域，没有重叠。如果允许重叠，那么（我相信）以下方法将覆盖整个区域，并且重叠最小。

正如你可能知道的那样，只有3个2D细化具有正多边形的空间 - 使用正方形，三角形或六边形。策略是使用这些多边形之一进行镶嵌细分，然后将圆圈限制到每个多边形。因此，从给定圆的半径计算所需六边形的大小，使用六边形镶嵌该区域然后在每个六角形上划一个圆圈。

注意： Eric Bainville a>建议采用类似的方法。

- Flaviu Cipcigan

How would an algorithm work that covers an arbitrary area with circles of equal radius?

The radius of the circle and the size and shape of the area are arbitrarily given. The area should be covered with as few circles as possible. The circles may overlap.

Is there an algorithm that will handle this?

解决方案

Hope I have understood your question right...

It can be proved that Hexagonal Close Packing (HCP) of spheres covers the maximum volume, using spheres. Therefore, I assume that doing HCP with circles will also cover the maximum area using circles. Tessellate your area with triangles and place a circle with the centre at each vertex of the triangle, with the radius half the length of the side of the triangle. See this for an image of the algorithm I am talking about.

Note: This is similar to the close packing of atoms in a unit cell.

EDIT: My previous method covers as much of the area as possible, without overlapping. If overlapping is allowed, then (I believe that) the following method would cover the whole area with minimum overlapping.

As you probably know, there are only 3 tessellations of 2D space with regular polygons - using squares, triangles or hexagons. The strategy is to tessellate using one of these polygons and then circumscribe a circle to every polygon. A hexagon would waste the minimum area using this method.

Therefore, from the radius of the given circle, calculate the size of the needed hexagons, tessellate the area using the hexagons and then circumscribe a circle onto each hexagon.

NB: Eric Bainville suggested a similar method.

-- Flaviu Cipcigan

这篇关于用等半径的圆覆盖任意区域的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！