PACK CIRCLES IN RECTANGLE CODE

The code is not optimized, to favor readability (or so I hope :)). Var placement = (this, surface) Ĭonsole.log ('placed',placement.length,'out of','for surface', surface) Surface += Math.PI * Math.pow(this.circles,2) find the smallest rectangle to fit all circlesįor (var i = 0 i != i++) return all placed circles except the four bounding circles match current circle against all possible pairs of placed circles

compute all possible placements of the unplaced circlesįor (var i = 0 i != unplaced.length i++) Var w = this.w = Math.sqrt (surface * this.ratio)

Var bounding_r = Math.sqrt(surface) * 100 // 'infinite' radius deduce starting dimensions from surface If (in_rect(radius, p2)) res.push(new Circle (radius, p2)) If (in_rect(radius, p1)) res.push(new Circle (radius, p1)) Var p2 = new Point (base.x +u.y * y, base.y - u.x * y) Var p1 = new Point (base.x -u.y * y, base.y + u.x * y) compute c1 and c2 intersection coordinates in (u,v) base Var u = c1.c.vect(c2.c) // c1 to c2 vector return the corner placements for two circles approximate a segment with an 'infinite' radius circleįunction bounding_circle (x0, y0, x1, y1) check if a circle is inside our rectangle try to fit all circles into a rectangle of a given surface Here is a fiddle var Packer = function (circles, ratio) I have added a simple dichotomic search on top of it to guess the minimal surface (which yields the smallest bounding rectangle for a given aspect ratio). (it simply tries to fit a bunch of circles into a given rectangle). The original algorithm does not produce the smallest rectangle to hold all the circles The algorithm simply starts with the four bounding circles and adds one circle at a time, using the greedy heuristic lambda parameter to pick the 'best' location. This also simplifies the start condition greatly. The 'corner' circles (as the algorithm calls them) are all computed as tangents to a pair of circles, thus eliminating the special circle+segment or segment+segment cases. They are computed to pass through the corners of the bounding box and converge toward the actual sides when the radius grows. The picture shows what the 4 bounding circles look like when the radius is decreased. Instead of segments defining the bounding box, I used circles with 'infinite' radii, that can be considered a good approximation of lines: I used a trick to make the computation more regular. I tweaked it quite a bit, but I think it does basically the same thing. Here is a go at the implementation of your algorithm.

Pack circles in rectangle