Covering an arbitrary region with circles of equal radius

Question

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

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

Is there an algorithm that will handle this?

Answer 1

I hope I understood your question correctly ...

It can be proved that the hexagonal closed packaging (HCP) of the spheres covers the maximum volume using spheres. Therefore, I assume that doing HCP with circles will also cover the maximum area with circles. Tessellate the area with triangles and place a circle with a center at each vertex of the triangle with a radius equal to half the length of the side of the triangle. See this for a picture of the algorithm I'm talking about.

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

EDIT: My previous method covers as much area as possible, without overlapping. If overlap is allowed, then (I believe that) the following method will cover the entire area with minimal overlap.

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 limit the circle to each polygon. Using this method, the hexagon will spend the minimum area.

Therefore, from the radius of the given circle, we calculate the size of the necessary hexagons, analyze the area using hexagons, and then draw a circle on each hexagon.

NB: Eric Bainville proposed a similar method.

-- Flaviu Cipcigan

Answer 2

I know that the question may be a bit outdated, but recently I had a similar problem with covering a geographic area with equal circles using a hexagonal grid, and that’s how I solved it:

• my input was the radius of the circle indicated in meters and the coordinates of the borders of the area.
• First I found a border rectangle that covers a given area
• Then, starting from the lower left level, I move the point at a distance equal to twice the height of the triangle used to build the hexagon (its side is the same in the radius of my circle) and the value is 0 degrees using Vincenti formulas
• for each point found, I check if it intersects with my input area, if I save it, otherwise I will skip it.
• when i got to the edge i do one more check to make sure i get all the points inside
• I move the point with 60 degrees, check it, then 120 degrees, check again
• go back to the third step, but now I move the points with 180 degrees
• and the rib will conduct another test again, and then, as in step 6, but first at 120 degrees, then at 60 degrees
• continue until you reach the top edge of the rectangle.

as in this image, of course, you can increase accuracy by reducing the radius of the circle

I know that this is not the best option, but for me it is very good.

I hope this is understandable and will help anyone.

Answer 3

Without knowing more about your limitations, I would suggest taking a regular covering of the plane, with disks corresponding to the usual hexagons of the hexagonal tile. Then save all disks that intersect the form.

Answer 4

I know that the question is to ask the algorithm, but I had a similar problem, to cover the US with circles, and I quickly found a solution using this free online tool . Therefore, I humbly suggest that if the area and radius have not changed, this can be done in about 3 minutes. Obviously, this answer is not generalized, but often the problems are not either.