I want an algorithm to place a number of arbitrary (with min,max) radius circles inside another shape, mainly inside a rectangle, without overlapping and (seemingly) random position.
You have two constraints:
Keeping circles away from each other
This one does not depend on details about the rectangle:
If the midpoints of the circles are closer to each other than the sum of their radiuses, the two circles intersect. Otherwise they do not (they may touch in case of equality). And you can use the Pythagorean theorem for calculating the distance.
If the radiuses are r1
and r2
, and the midpoints are x1,y1
and x2,y2
, the check would look like
if(Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)) >= r1+r2)
okay
else
not okay
where Math.sqrt()
calculates the square root of something (and calculcating the second power is done with simple multiplication here).
Keeping circles inside a rectangle
Here the radius has a role again: if the midpoint of a circle is closer to any border than its radius, it intersects with that border.
The simplest case is when the rectangle is axis-aligned, and starts from 0,0
. In this case it is pretty obvious that a circle with radius r
and midpoint x,y
can not have x<r
or y<r
, because in that case the circle would have some part in the negative x or y planes. The other limits are the width
and height
of the rectangle, x+r>width
(or rather x>width-r
) would result in the circle having some part "beyond" the limits of the rectangle.
This can be easily extended to an axis-aligned rectangle running from x1,y1
to x2,y2
:
if( x>=x1+r && x<=x2-r && y>=y1+r && y<=y2-r )
okay
else
not okay
However in reality you would not use this check, but generate circles which are inside a rectangle:
r
(between suitable min and max)x1+r, y1+r
and x2-r, y2-r
So it is just the classic task of generating a random number between some limits. If you happen to have a random number generator function random()
generating fractions between 0 and 1, and limits min
and max
, min+(max-min)*random()
is the expression you could use.
Put together in JavaScript:
function stuff(){
let ctx=cnv.getContext("2d");
ctx.clearRect(0,0,cnv.width,cnv.height);
lineStyle="black";
ctx.strokeRect(0,0,cnv.width,cnv.height);
let x1=ix1.valueAsNumber,y1=iy1.valueAsNumber;
let x2=ix2.valueAsNumber,y2=iy2.valueAsNumber;
let cnt=icnt.valueAsNumber;
let rmin=irmin.valueAsNumber,rmax=irmax.valueAsNumber;
ctx.fillStyle="lightgray";
ctx.fillRect(x1,y1,x2-x1,y2-y1);
ctx.fillStyle="blue";
let giveup=Date.now()+3000;
let circles=[];
while(circles.length<cnt && Date.now()<giveup){
let r=rmin+(rmax-rmin)*Math.random();
let x=x1+r+(x2-r-x1-r)*Math.random();
let y=y1+r+(y2-r-y1-r)*Math.random();
let okay=true;
for(let c of circles)
if(Math.sqrt((x-c.x)*(x-c.x)+(y-c.y)*(y-c.y))<r+c.r){
okay=false;
break;
}
if(okay){
circles.push({x:x,y:y,r:r});
ctx.beginPath();
ctx.arc(x,y,r,0,Math.PI*2);
ctx.fill();
ctx.stroke();
}
}
ctx.strokeRect(x1,y1,x2-x1,y2-y1);
}
stuff();
input{width:50px}
x1:<input id="ix1" type="number" min="0" max="600" value="50" onchange="stuff()">
y1:<input id="iy1" type="number" min="0" max="150" value="10" onchange="stuff()">
x2:<input id="ix2" type="number" min="0" max="600" value="400" onchange="stuff()">
y2:<input id="iy2" type="number" min="0" max="150" value="140" onchange="stuff()">
#:<input id="icnt" type="number" min="0" max="50" value="10" onchange="stuff()">
rmin:<input id="irmin" type="number" min="1" max="50" value="20" onchange="stuff()">
rmax:<input id="irmax" type="number" min="1" max="50" value="50" onchange="stuff()">
<canvas id="cnv" width="600" height="150"></canvas>
As it is easy to pick parameters which are either unsolvable at all, or can be unsolvable after placing the first few circles in an unfortunate way, the code has a time limit, and gives up the work after 3 seconds.