Sunday 19 June 2016

geometry - 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 imageenter image description here :



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 :



enter image description here



So thanks again ..


Answer



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

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.


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...