[ACCEPTED]-Covering an arbitrary area with circles of equal radius-geometry

Accepted answer
Score: 13

I know that question may be a bit outdated 9 but recently I got a similar problem with 8 covering geographic area with equal circles 7 using hexagonal grid and this is how I solved 6 it:

  1. my input data were radius of circle given in meters and coordinates of borders of the area
  2. first I found the bounds rectangle that covers given area
  3. then starting from the left bottom I move the point by distance equaling double the height of the triangle used to build the hexagon (its side is the same of radius of my circle) and bearing of 0 degrees using Vincenty's formulae
  4. for each point I found, I check if it intersects with my input area, if does I save it, other way I skip it
  5. when I got to the edge I do one more check to ensure that I will get all points within the are
  6. I move the point by bearing of 60 degrees, check it, then by 120 degrees, check again
  7. go back to 3rd step but now I move the points by bearing of 180 degrees
  8. and the edge again one more check and then like in step 6th but first 120 degrees then 60 degrees
  9. continue until you got to the top edge of rectangle

diagram of algorithm like in given image, of course you can 5 increase the accuracy by decreasing radius 4 of circle

I know that this is not the best 3 option but it works pretty well for me.

I 2 hope it's quite understandable and will 1 help anyone.

Score: 9

Hope I have understood your question right...

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

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

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

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

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

NB: Eric Bainville suggested 1 a similar method.

-- Flaviu Cipcigan

Score: 1

Without knowing more about your constraints, I 4 would suggest taking a regular covering 3 of the plane, with disks corresponding to 2 the regular hexagons of an hexagonal tiling. Then 1 keep all disks intersecting the shape.

More Related questions