# Packing problem -uniform distribution by Percentage of coverage - circles on a plane .

EDIT :

After reading the comments, I understood that in fact, my question was not so clear . so I will put it in simple terms of programming :

First Scenario :

My Input :

$a = Plane area [ nominally X,Y ] . $r == Circles ( "dots" or "discs" ) Diameter or radius [r or d].

per == Wanted Coverage in percentage . ( desired ) Output : An array of aligned ( x-axis && Y-axis ) circles with given radius ( r ) distributed in $row,$column to cover the exact wanted percentage ( $per ) . $d_y == $d_x == distance in horizontal,vertical ( uniform distance for $row, $column ) Unknown : $d_y == $d_x == distance in horizontal,vertical Problem : Given $a , $r and $per , what are the distribution distances between the circles ( $d_y, and $d_x ) that will result in a coverage of exact $per of $a .

Second Scenario ( derivative )

Input :

$a = Plane area [ nominally X,Y ] . $d_y, $d_x = Distances between circles ( "dots" ) on x, y axis . $per = Wanted Coverage in percentage .

( desired ) Output :

An array of aligned ( x-axis && Y-axis ) with radius $r circles with the given distances between $row and $column, that will result in a coverage of exact $per of $a . Problem : Given $d_y , and $d_x , What is the Circle's ( "dots" or "discs" ) Diameter or radius [$r or d] that will result in a coverage of exact $per of $a .

Unknown :

$r = Circle's diameter or radius . Original Question : So, first, I am not a mathematician, and I only encounter kids-level math on my daily work when programming. I need to write a simple CAD macro that given a wanted percentage coverage of a plane, and the diameter ( or radius ) of a "dot", actually a circle , will distribute the points in such distances to allow the exact wanted coverage percentage . In other words : given the percentage of wanted coverage , circles size and plane size , what is the distance between the points ( straight line circumference , not center if possible ) Or with a simple image : Given Y,X of a plane and [r] of circle, and wanted coverage percentage of plane by "dots" or circles ( say 32% ) how to know the distance D[H] - horizontal and D[V]- vertical I know I also need to assume that the "dots" center in edge rows are on the edge itself, or alternative the distance from edges is equal to the distance between them .. If it were a square and not a circle, I could have managed with very simple calculations . But now I am not sure of myself . Does calculating the circle area πr2 and subtracting from the coinciding square and then distribute the squares will work ? (Later I also need the reverse - given the distances and the percentage - calculate the circles diameter ( or r ) ( I found this "circle packing" article on wikipedia - but it does not address the wanted distances ) last Edit ( result ) I ended up using some combination of the first answer by Kimchi lover and second Ross Millikan . Both valid as far as my non-mathematical self can understand .(too bad can only accept one .. ) I thought I would post The result ( which is not final - but works ) , so to show what your help produced : So thanks again .. ## 2 Answers I hope I have understood what is giving you difficulty. In terms of your rewrite, the symbols I use here match up with yours as follows:$$d_x = H,\space d_y = V,\space \mathrm {per} = C$$ For starters, with a rectangular grid as illustrated, you want$\pi R^2 / (V\times H) = C$, where$C$is the desired fractional coverage ($.33,$say),$R$is the dot's radius, and$V$and$H$are the vertical and horizontal spacings. Everything is specified except the$H$and$V$parameters. This is assuming that$H>R$and$V>R$, so the dots don't overlap. Then$HV =\pi R^2 / C$is what you want. To get a square grid,$H=V=\sqrt{\pi R^2 / C}.$The densest you can get this way is$\pi/4\approx.785$. To use this to draw the dots, for each integer$m$and$n$, put a dot of radius$R$with center at$(mH,nV)$. Or for integer$m$and$n$in the range$1\le m \le M$and$1\le n \le N$put a dot. Now the$MN$dots have the desired density in a$(M+1)H\times(N+1)V$rectangle. An equilateral triangular grid will allow denser dot placement and a different set of formulas. Here the$(m,n)$-th dot is centered at$((m+n/2)H, n (\sqrt 3 / 2)H)$, with$C= \pi R^2/ (H^2 \sqrt 3 / 2)$. The fundamental region is an equilateral triangle, with side length$H$. This is what you get if you put a dot at the center of each hexagon in a honeycomb grid. The dots don't overlap condition is$2R<H$. Describing the$(m,n)$for which the dots land in your area$a$is more intricate, so I'll skip that issue. In general, the coverage$C$is the ratio of the area of a dot to the area of the fundamental region of the pattern of dots. In the edited version of the problem, both scenarios are covered by the equation$\pi R^2 / (V\times H) = C$but in scenario 1 the unknowns are$H$and$V$and in scenario 2,$R$is the unknown. • How do you determine the number of dots in each row and column? – uniquesolution Jul 24 '17 at 13:16 • @uniquesolution There are 2 questions here: how do you determine the spacing of the dots to get the desired coverage, and how large pattern do you want. You comment addresses the latter. The answer: whatever you, or the customer, or the job spec says. If the dots are really cookies, the size of the cookie sheet will determine$M$and$N$. (I edited my answer to catch a math typo your question revealed: thanks!) – kimchi lover Jul 24 '17 at 13:24 • As far as I can understand, the customer's input is only this: rectangle dimensions$x\times y$and a radius$r>0$. Consequently,$M,N$should be part of the answer, which - of course - makes the question not well posed. – uniquesolution Jul 24 '17 at 13:28 • @uniquesolution You are right: its not a well posed math problem. It's obvious the OP is operating outside of their comfort zone, so it makes sense to give a little slack. They are probably not aware of the boundaries between the math content and the CAD aspect of the real problem, and the posed question is almost certainly wrong in some aspect. But I think my answer might elicit more information, or help the OP reformulate, or whatever. – kimchi lover Jul 24 '17 at 13:54 • @kimchilover 1 - thanks for your great answer ,it is a bit more clear now. 2 - I also like kimchi :) . 3 - can you elaborate on the triangular grid ? I am not constrained to a single one grid 4. see my edit – Obmerk Kronen Jul 24 '17 at 15:32 For your first scenario: Each disk covers an area of$\pi r^2$, so covers$\frac {\pi r^2}a$of your area. Divide this into your desired coverage to find the number of disks to use. The maximum number of disks you can put in one horizontal line is$\frac X{2r}$because they will touch otherwise. Similarly the maximum number you can put vertically is$\frac Y{2r}$Choose a rectanglar arrangement that gives the right number of disks. If there are$n$disks horizontally and you want the outer margins to be half the spacing between disks, you have$nDH$in empty space and$2rn$in diameters of the disks, so$nDH+2rn=X, DH=\frac {X-2rn}n$and similarly in the other direction. For your second scenario: You have$n$disks in a horizontal row where$n=\frac X{dx}-1$because you have spaces outside the row of disks. Similarly you have$m$vertical, so a total of$nm$disks. The total area is then$nm\pi r^2$. Choose$r\$ to be the proper fraction of the total area.

• Thanks , this seems much more intuitive method , but somehow something was not clear . I ended up using a mix of both methods . Thanks again for the great help . – Obmerk Kronen Jul 26 '17 at 14:24