views:

307

answers:

6

Given n circles with radii r1 ... rn, position them in such a way that no circles are overlapping and the bounding circle is of "small" radius.

The program takes a list [r1, r2, ... rn] as input and outputs the centers of the circles.

  1. I ask for "small" because "minimum" radius converts it into a much more difficult problem (minimum version has already been proved to be NP hard/complete - see footnote near end of question). We don't need the minimum. If the shape made by the circles seems to be fairly circular, that is good enough.
  2. You can assume that Rmax/Rmin < 20 if it helps.
  3. A low priority concern - the program should be able to handle 2000+ circles. As a start, even 100-200 circles should be fine.
  4. You might have guessed that the circles need not be packed together tightly or even touching each other.

The aim is to come up with a visually pleasing arrangement of the given circles which can fit inside a larger circle and not leave too much empty space. (like the circles in a color blindness test picture). alt text

You can use the Python code below as a starting point (you would need numpy and matplotlib for this code - "sudo apt-get install numpy matplotlib" on linux)...

import pylab
from matplotlib.patches import Circle
from random import gauss, randint
from colorsys import hsv_to_rgb

def plotCircles(circles):
    # input is list of circles
    # each circle is a tuple of the form (x, y, r)
    ax = pylab.figure()
    bx = pylab.gca()
    rs = [x[2] for x in circles]
    maxr = max(rs)
    minr = min(rs)
    hue = lambda inc: pow(float(inc - minr)/(1.02*(maxr - minr)), 3)

    for circle in circles:
        circ = Circle((circle[0], circle[1]), circle[2])
        color = hsv_to_rgb(hue(circle[2]), 1, 1)
        circ.set_color(color)
        circ.set_edgecolor(color)
        bx.add_patch(circ)
    pylab.axis('scaled')
    pylab.show()

def positionCircles(rn):
    # You need rewrite this function
    # As of now, this is a dummy function
    # which positions the circles randomly
    maxr = int(max(rn)/2)
    numc = len(rn)
    scale = int(pow(numc, 0.5))
    maxr = scale*maxr

    circles = [(randint(-maxr, maxr), randint(-maxr, maxr), r)
               for r in rn]
    return circles

if __name__ == '__main__':
    minrad, maxrad = (3, 5)
    numCircles = 400

    rn = [((maxrad-minrad)*gauss(0,1) + minrad) for x in range(numCircles)]

    circles = positionCircles(rn)
    plotCircles(circles)

Added info : The circle packing algorithm commonly referred to in google search results is not applicable to this problem.

The problem statement of the other "Circle packing algorithm" is thus : Given a complex K ( graphs in this context are called simplicial complexes, or complex in short) and appropriate boundary conditions, compute the radii of the corresponding circle packing for K....

It basically starts off from a graph stating which circles are touching each other (vertices of the graph denote circles, and the edges denote touch/tangential relation between circles). One has to find the circle radii and positions so as to satisfy the touching relationship denoted by the graph.

The other problem does have an interesting observation (independent of this problem) :

Circle Packing Theorem - Every circle packing has a corresponding planar graph (this is the easy/obvious part), and every planar graph has a corresponding circle packing (the not so obvious part). The graphs and packings are duals of each other and are unique.

We do not have a planar graph or tangential relationship to start from in our problem.

This paper - Robert J. Fowler, Mike Paterson, Steven L. Tanimoto: Optimal Packing and Covering in the Plane are NP-Complete - proves that the minimum version of this problem is NP-complete. However, the paper is not available online (at least not easily).

+7  A: 

Not a solution, just a brainstorming idea: IIRC one common way to get approximate solutions to the TSP is to start with a random configuration, and then applying local operations (e.g. "swapping" two edges in the path) to try and get shorter and shorter paths. (Wikipedia link)

I think something similar would be possible here:

  1. Start with random center positions
  2. "Optimize" these positions, so there are no overlapping circles and so the circles are as close as possible, by increasing the distance between overlapping circles and decreasing the distance between other circles, until they're tightly packed. This could be done by some kind of energy minimization, or there might be a more efficient greedy solution.alt text
  3. Apply an iterative improvement operator to the center positons
  4. Goto 2, break after a maximum number of iterations or if the last iteration didn't find any improvement

The interesting question is: what kind of "iterative improvement operator" could you use in step 3? We can assume that the positions at that stage are locally optimal, but they might be improved by rearranging a large fraction of the circles. My suggestion would be to arbitrarily choose a line through the circles. Then take all the circles "left" of the line and mirror them at some axis perpendicular to that line: alt text You would probably try multiple lines and pick the one that leads to the most compact solution.

The idea is, if some of the circles are already at or close to their optimal configuration, chances are good this operation won't disturb them.

Other possible operations I could think of:

  • Take one of the circles with the highest distance from the center (one touching the boundary circle), and randomly move it somewhere else: alt text
  • Choose a set of cirlces that are close to each other (e.g. if their centers lie in an randomly chosen circle) and rotate them by a random angle.
  • Another option (although a bit more complex) would be to measure the area between the circles, when they're tightly packed:

alt text

Then you could pick one of the circles adjacent to the largest between-circle-area (the red area, in the image) and swap it with another circle, or move it somewhere to the boundary.

(Response to comment:) Note that each of these "improvements" is almost guaranteed to create overlaps and/or unneccessary space between circles. But in the next iteration, step 2 will move the circles so they are tightly packed and non-overlapping again. This way, I can have one step for local optimizations (without caring about global ones), and one for global optimizations (which might create locally suboptimal solutions). This is far easier than having one complex step that does both.

nikie
The line mirroring is a nice idea for making global changes without scrambling local optimisations, but could of course create overlaps.
Chris Johnson
Some excellent ideas here nikie... I will try to combine them (if possible) with rafe's approach and see where that leads.
Rajan
+5  A: 

Can you treat the circles as charged particles in a charged cavity and look for a stable solution? That is, circles repel one another according to proximity, but are attracted towards the origin. A few steps of simulation might get you a decent answer.

Rafe
Thats a pretty cool idea.
Rajan
This sounds promising to me, especially when coupled with some sort of annealing schedule ( http://en.wikipedia.org/wiki/Simulated_annealing ) which introduces random noise to mix up the particles early in the simulation, and (continuing the charge analogy) tightens up the potentials to nearly a square-well late in the simulation to enforce the no-penetration and global-circular-shape constraints more accurately.
Chris Johnson
This answer is the sort of 'energy minimization' that could be used as step 2 of nikie's answer.
Chris Johnson
@Chris Johnson: Exactly. I imagined that every circle would be attracted to the center, and that two circles would be repel each other as soon as they start to overlap. But I guess the results would be more or less the same.
nikie
+1  A: 

Sounds like a Circle Packing problem, here is some information:

martinus
@Martinus : The circle packing algorithm commonly referred to in google search results is not applicable to this problem. That algorithm starts from a planar graph and derives its corresponding "circle packing". This is the application of the "Circle packing theorem" by Thurston. However, we do not have a planar graph to start from. If we had the planar graph, it would have been a polynomial time algo to find the circle packing. In its generic form, this problem is NP complete .
Rajan
The problem statement of the other "Circle packing algorithm" is thus : Given a complex K (graph K) and appropriate boundary conditions, compute the radii of the corresponding circle packing for K.... It basically starts off from a graph telling which circles are touching each other (vertices of the graph denote circles, and the edges denote touch between circles). But the vertices and edges are arbitrarily placed in space. One has to find the circle radii and positions so as to satisfy the touching relationship denoted by the graph. Not the same as our problem.
Rajan
A: 

You could try using a 2d physics library, and just pour your 2d circles into a larger circular container - and wait for them to settle into place.

Michael Anderson
+4  A: 

I have a pretty naive one pass (over the radii) solution that produces alright results, although there is definitely room for improvement. I do have some ideas in that direction but figure I might as well share what I have in case anybody else wants to hack on it too.

alt text

It looks like they intersect at the center, but they don't. I decorated the placement function with a nested loop that checks every circle against every other circle (twice) and raises an AssertionError if there is an intersection.

Also, I can get the edge close to perfect by simply reverse sorting the list but I don't think the center looks good that way. It's (pretty much the only thing ;) discussed in the comments to the code.

The idea is to only look at discrete points that a circle might live at and iterate over them using the following generator:

def base_points(radial_res, angular_res):
    circle_angle = 2 * math.pi
    r = 0
    while 1:
        theta = 0
        while theta <= circle_angle:
            yield (r * math.cos(theta), r * math.sin(theta))
            r_ = math.sqrt(r) if r > 1 else 1
            theta += angular_res/r_
        r += radial_res

This just starts at the origin and traces out points along concentric circles around it. We process the radii by sorting them according to some parameters to keep the large circles near the center (beginning of list) but enough small ones near the beginning to fill in spaces. We then iterate over the radii. within the main loop, we first loop over points that we have already looked at and saved away. If none of those are suitable, we start pulling new points out of the generator and saving them (in order) until we find a suitable spot. We then place the circle and go through our list of saved points pulling out all of the ones that fall within the new circle. We then repeat. on the next radius.

I'll put some ideas I have into play and make it mo`bettah. This might serve as a good first step for a physics based idea because you get to start with no overlaps. Of course it might already be tight enough so that you wouldn't have much room.

Also, I've never played with numpy or matplotlib so I write just vanilla python. There might be something in there that will make it run much faster, I'll have to look.

aaronasterling
This looks awesome. It reminds me somewhat of the escher hyperbolic disk because of the concentration of the large circles near the center. I guess that can be changed if needed without affecting the algo too much (I still am trying to understand your algo, so I might be wrong).Also, I am using numpy and matplotlib only for plotting the picture. They don't do any processing in my stub.
Rajan
I am curious... How many circles are there in your picture? And how long did it take to generate this output?
Rajan
@Rajan, there's 400 circles in the picture. It takes a few minutes on my machine but my machine is slow so you'll probably not have to wait too long. It's no good for doing it, say, real time for a web service unfortunately . To run it, just copy and paste the code from the link over the stub function that you provided and you're good to go.
aaronasterling
I think this wont work without the "main" part of your code.
Rajan
@Rajan, the whole code is available at the link in the first paragraph of my post. It's at http://pastebin.com/VciE4Js7. It's about 124 lines so I didn't want to put it here. Note that it's not close to fully tuned, I'm still in the "make it work" phase ;) It should work as either a standalone module that exports the `positionCircles` function or just pasted over the stub function that you provide.
aaronasterling
A: 

http://en.wikipedia.org/wiki/Apollonian_gasket

This seems somewhat relevant to what you are trying to do, and may provide some potential constraints for you.

q__
I am not sure how to use the gaskets, but they are beautiful. Thanks for posting it.
Rajan
I think this can work in specific cases of input: generate an Apollonian gasket from the three largest curvatures/radii input, and then note the curvatures/radii that are generated subsequently. If the rest of the radii supplied correspond to radii that are equal or less than the generated radii, then you can simply draw the circles concentric where you expect to find the generated circles in the gasket. It's not a very nice solution, however, but it might provide some extra insight, perhaps.
q__