CODEWITHSUNDEEP
javascriptmathoptimizationgeometry
Rob
Rob

Reputation: 11788

How to arrange circles to use lowest possible space?

I'm building a configuration tool with Javascript that calculates the measurements of a cable trunc in different ways. Basically, you can enter the amount of cables and the cable diameter. Now I want to visualize these cables as circles with the given diameter and automatically pack them together to take up as little space as possible. Here are two examples:

7 cables packed together:

7 cables

48 cables:

48 cables

As you can see, I already tried to achieve that by using a physics engine (physics.js) and let gravity automatically arrange the elements optimally. This somehow works for small numbers but it takes quite a while to finish for larger numbers of elements ( > 20) and it doesn't always produce the best possible result. Besides that, I think that this way is a little over the top.

Is there a neat way of calculating the position of x given circles with diameter d? Is there perhaps even a framework or similar that takes care of such tasks? I'm curious about your ideas, thanks in advance. Oh, and by the way, this isn't homework - I'm 35+ :-D

Upvotes: 2

Views: 2949

Answers (2)

Escualo
Escualo

Reputation: 42072

If by "lowest possible space" you mean "contained in the smallest area" (or "enclosed by the tightest convex hull"), you may find it useful to check the article in Wikipedia about circle packing:

In two dimensional Euclidean space, Joseph Louis Lagrange proved in 1773 that the lattice arrangement of circles with the highest density is the hexagonal packing arrangement, in which the centres of the circles are arranged in a hexagonal lattice (staggered rows, like a honeycomb), and each circle is surrounded by 6 other circles.

Circle Packing In Hexagonal Lattice

Could you base your algorithm on this finding? What I am thinking is this: start with the "trivial" hexagon arrangement that covers at least the number of cables, and then start iterating over the outer circles and remove the one which is the farthest from the center circle. Continue until you are left with the exact number of circles you needed.

If you do this, you save the time of computing "what you already know". That is, if you had seven circles, you know that it is a hexagon with a circle in the middle, period. If you had eight circles, you start with the hexagon of 12 circles, which contains the hexagon of six circles, which contains the one circle: a total of 19 circles (12 + 6 + 1). You start removing circles from the outer hexagon (the one with 12 circles) until you have removed 11, and you are left with 8 circles (1 + 6 + 1) in optimal arrangement.

Upvotes: 2

Philipp
Philipp

Reputation: 69663

This algorithm will not always find the proven best solution (which is quite hard, because for most numbers over 13 the best known configuration has not yet been proven to be ideal), but in most cases it should at least give a solution which is "quite good":

  • Start with one center-circle and place it
  • for each additional circle
    • find the angle from where it gets closest to the center-circle without overlapping an already placed circle
    • place it there

The time-complexity of this algorithm depends on how efficiently you can find the closest position for a new circle. With some optimizations you should be able to get this to be linear to the number of circles. That would mean that the overall complexity of the algorithm would be n².

Upvotes: 2

Related Questions