Programming assignment

Question

JavaScript

The problem concerns SVG and JS, but that's not the point. I'm racking my brains on how best to solve the following problem: there is a rectangle MxN, there is an array of radii of circles. The customer wants to place them in this rectangle so that circles with larger radii are closer to the center, and smaller ones are closer to the edges. It is necessary to calculate the coordinates of the centers so that the circles do not overlap each other. Most likely you will need small indents between the circles.
Maybe there is some old-fashioned algorithm for this?
Thank you.

Answer 1

I think you can try the following. When three circles with radii a , b , c touch, their radii form a triangle with sides a+b , b+c and c+a . (The radii of the tangent circles lie on one straight line, hence one step to the triangle.)
Knowing the sides of the triangle, we can calculate its angles. Let's first calculate the angle at the center a . Take the next circle d and attach it to a and c . Another triangle is formed from circles a , c and d. We can again calculate its angle. Obviously, we can stack circles around a in this way until the sum of the interior angles exceeds 360 degrees. After that, we can start laying down the remaining circles around b . By this time, a part of the circle will already be occupied by him - circles a , c and, possibly, the last circle laid on the other side of a . By knowing the sides and angles we know the center of the circle and thus its vertical and horizontal boundaries. During the laying process, you can track the maximum border so that you do not inadvertently go beyond the size of the rectangle. It may make sense to add imaginary filler circles as you work.

This is not a complete solution (I will not offer an algorithm other than enumeration, in addition, there are options when a small circle can be inserted between three tangent circles, so the algorithm may be quite complicated). But the start seems to be good.

Answer 2

Well, sort the radii in ascending order. Then greedily shove the largest radius into the center of the rectangle. Then the next one and see if the circles intersect. They will intersect (or rather, one circle will be inside the other), so we move the second radius somewhere until they intersect (look here http://e-maxx.ru/algo/circles_intersection ).
It?

Answer 3

This is? habrahabr.ru/post/175719/