Ideas for an algorithm for random distribution of

问题:

I am searching for a concept to distribute circles in a square randomly, so that they dont overlap. All circles are of the same size. The area covered by the circles can be high, up to the theoretical maximum of ca. 90 % of the square (in which they are completely ordered). About 200 circles should be placed and I want to specify the number of circles exactly. (The distribution is needed as input for a model generation of a FE-analysis, btw)

With a straight-forward algorithm that places circles sequentially on a free spot, it is not possible to cover more than about 54%, which is not a surprise, as at some point there is just no space left. Therefore previous SO-threads do not really cover my issue (getting close: Placing random circles without overlap (and without using brute force)?)

With a simple random displacement of the circles of an ordered set of circles, the distribution seems to be "not random enough".

All concepts, I came up with so far, feel either to complicated or to brute-force-style. The approach I like most is to determine all possible positions on which the next circle can be placed, so that the left-over space is big enough to place the remaining circles. Then pick one of these positions randomly and so on. But: To determine the "capacity" of the left-over space is not easy and numerically very complex. I dont really know how to do it, and whether it can be done with reasonable numerical effort.

Second idea is a billard simulation: Place all circles in a whatever pattern and simulate a big pool billard. Pretty brute force and numerically very costly as well. I am a bit afraid of descretization issues as well.

Number 3 is more mathematical and is based on defining a potential field for every circle with a random "strength", so that there is some kind of gravitation between the circles and calculate the equilibrium state. The development of a mathematical model for this is not trivial and would be quite a mission...

So - finally - the question: What are your suggestions to solve the problem as leightweight as possible? Do you know algorithms I should look at to solve this? What are your remarks to my ideas?

Thank you all a lot in advance! I am excited to read your answers.

回答1:

Start by using the basic algorithm to draw as many as possible circles that don't collide. When it finishes (and it can't reach 200 circles), start pushing in circles. I mean physically push them in with a physics engine: http://www.sgtconker.com/2010/09/article-xna-farseer-platform-physics-tutorial/ (without using gravity).

回答2:

2 ideas:

Instead of thinking of the square as a closed box, take the top away and allow the circles to fall under the effects of gravity into the open box. By altering the position of the circles before they fall you create randomness. This might be the same or similar to your billards example.

or

Use Quadtrees to divide up the space in the box and place randomly checking for overlap using collision detection, which in this case might only need to be the center of the circle to another center is greater than double the radius and the walls of the box are greater than a radius away. By using quadtrees this will make the algorithm more efficient.

回答3:

Maybe you can find a geometrical property that is true only for 200-packings and not for 199-or-less-packings. Then build the packing incrementally while conserving the property.

For example, you may examine several available 200-packings and measure the maximal distance between all circle centers -- m. Then construct a packing incrementally, preserving m.

I don't know how often such a construction succeeds, but you can add more invariant properties as you wish to increase the chance of success.

回答4:

If you'll sometimes have a high number of circles such that you are close to, or at, maximal packing, the best solution is to start with your circles maximally packed in some corner (which I guess is hexagonal packing) and then do a physical simulation where you add some "temperature", i.e. you randomly kick some circles and let them collide for some finite time.

I am afraid that with the other methods you might never be able to fit all your circles if you have so many circles that any valid solution would be close to maximal packing.

回答5:

Suppose you want n = 200 circles. My suggestion is to pick a number moderately larger than n, say m = 300, and generate that many points at random locations within the square. This set of m points is your candidate set of circle centres. Now produce a graph containing m vertices, one for each point, in which two vertices are linked by an edge if and only if the distance between their points is less than the circle diameter -- it is exactly in this situation that we would be forbidden to include both circles in the solution, because they would overlap.

You can now model the problem of choosing which candidate circle centres should actually become circles as a maximum independent set problem: find a maximum-sized set of vertices in this graph having the property that no two vertices in the set are linked by an edge. This will find a set of circle centres such that no two of their circles would overlap. If this set contains more than n circles, then discard a random selection of circles until just n remain. If fewer than n circles are found, you'll need to increase m and try again.

Unfortunately the maximum independent set problem is NP-hard, so I don't know whether it will be feasible to solve on a 300-vertex graph. (And in turn, I don't know whether 300 random centres will give you enough flexibility to find 200 non-overlapping circles...) But in any case, you would normally solve maximum independent set in one of two ways:

1. Look for a minimum vertex cover, then take every other vertex to be the maximum independent set
2. Produce the complement graph (i.e. the graph in which two vertices are linked by an edge if and only if they are not linked by an edge in the original graph), and then find a maximum clique in this graph

Those Wikipedia pages contain links to papers describing algorithms for these problems that, while still exponential-time, are much faster than a standard "full backtracking" algorithm. A couple of things to bear in mind:

• You don't actually need the provably maximum independent set, just one >= n. So heuristics may be just fine; note the particularly simple heuristic for minimum vertex cover on the Wikipedia page.
• Beware the difference between "maximal" (easy) and "maximum" (hard) cliques/covers/independent sets!

回答6:

@toto2 @cyborg @TokenMacGuy

Update:

I have implemented the billard solution with the FarseerPhysicsEngine and played around with it a bit. Within the process of implementing the solution I modified the problem a bit :): Instead of keeping all circles inside the box, I allow the circles to move outside the border and let the outside part reappear on the opposite side (pretty much like in the oldschool asteroids game). This makes my distribution suitable for infinite repetition in x and y direction, which is even better for the underlying Finite Element modelling task. This comes along with some other issues regarding the physics simulation, and as this was not part of the original question, I will only describe those, if anyone is particularly interested.

So what I did: I order as many circles as wanted or as fit in the most dense order possible (where the centres of the circles are in a hexagon order). I leave a margin around the circles to make the simulation more stable. It sometimes happens, that circles overlap otherwise. Every circle gets a random velocity vector and mass. Everything else is collision detection and handling, done by the physics engine.

The outcome: It works well for high amounts of circles.

If performed with a small number of circles, they tend to stick together. I cant really explain why. Might be that Fraseer doesn't model the collision as ideally elastic, so that energy is dissipated. I don't know whether, and if where, there is a property for that. As I set friction to zero for the movement, this could lead to this kind of clustering:

Anyway, I am quite happy with the result for many circles and - as this was the unsolved part so far, I suppose this will do. It's a shame, that I don't have the time to dig deeper into the other concepts, although I will for sure have a deeper look at them later on.

Thank you all for participating!! Was fun to get all your input! If you have further ideas or comments on the solution, please let me know.