algorithmmathgeometrycircle-pack

Place arbitrary sized circles in another shape/parallelogram


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.


Solution

  • You have two constraints:

    1. Circles should remain inside a rectangle
    2. Circles should not overlap

    Keeping circles away from each other

    This one does not depend on details about the rectangle:

    Circles

    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.

    Rectangle-Circle

    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:

    1. pick a radius r (between suitable min and max)
    2. pick a point from the reduced rectangle with corners 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.