1

I'm trying to work out how to write an algorithm to randomly place circles of R radius, in a 2d rectangle of arbitrary dimensions, such that each placed circle is at least D distance away from other circles in the rectangle,

The rectangle doesn't need to be filled, to be more specific older circles may be destroyed, so I need to be able to place a new circle that respects the positions of the last N circles I've already placed (say 5 for eg), if it can't satisfy these conditions then I could handle it seperately.

Can anyone help me how to deduce such an algorithm, or perhaps point to some research that may cover this?

Improve this question
5
  • Do you have to 'fill' the rectangle? Your problem isn't very well described. You could place one circle at a random position and that would satisfy the requirements. Commented Sep 11, 2011 at 17:30
  • A goal of maximizing the number of circles seems to be implied. Commented Sep 11, 2011 at 17:41
  • The rectangle doesn't need to be filled, to be more specific older circles may be destroyed, so I need to be able to place a new circle that respects the positions of the last N circles I've already placed (say 5 for eg), if it can't satisfy these conditions then I could handle it seperately. Commented Sep 11, 2011 at 17:42
  • Nothing to do with C++, and nothing to do with computer programming languages. This is about maths. Commented Sep 11, 2011 at 17:53
  • This math.stackexchange question asked recently is similar, with a Poisson-disk paper mentioned. Commented Sep 12, 2011 at 7:08

4 Answers 4

Reset to default
1 
1 Place circle at random location 2 Loop over previous circles 3 if too close 4 delete new circle 5 goto 1 6 if need more circles 7 goto 1

To determine if there is room

Choose resolution required, say delta = D/100 for( x = 0; x < rectangle_size x += delta ) for( y = 0; y < rectangle_size y += delta ) unset failed loop over circles if x,y less than 2D from circle set failed break from circle loop if not failed return 'yes there is room' return 'no, there is no room'

If you expect to have so many circles that there only a few holes left with room for new circles, then you could do this

clear candidates Choose resolution required, say delta = D/100 for( x = 0; x < rectangle_size x += delta ) for( y = 0; y < rectangle_size y += delta ) unset failed loop over circles if x,y less than 2D from circle set failed break from circle loop if not failed add x,y to candidates if no candidates return 'there is no room' randomly choose location for new circle from candidates
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thanks for the reply, I'd like to try and avoid an iterative solution if possible as it doesn't tell me if it's not possible, and is not guaranteed to find a solution, or may take an inordinate amont of time
Determining if it is possible, that there is room for another circle, is a different problem. If you are adding so many circles that this is an issue, then you are not placing them at random, you are packing them.
0 
1. Pick random startingspot. 2. Place circle 3. Move in random direction at least D 4. Goto 2 until distance to edge is < D or the distance to another circles center is < 2D
Improve this answer

Comments

0

The first algorithm to come to mind is simulated annealing. Basically, you start out with the easiest solution, probably just a grid, then you "shake the box" in random ways to see if you get better answers. First you do large shakes, then gradually make them smaller. It sounds a little chaotic, and doesn't always produce the absolute best solution, but when something is computationally intensive it usually comes pretty close in a lot shorter time.

Improve this answer

Comments

0

It really depends on what you mean by "random". Assuming that you want as close to a uniform distribution as possible, you will probably have to use an iterative solution like the one ravenspoint suggested. It may be slightly faster to place all of the circles randomly and then start replacing circles that don't meet your distance condition.

If the randomness isn't that important - i.e. if it just has to "look" random (which is probably fine if you're not doing something scientific), then grid your space up and place your N circles by choosing N indices in the grid. You could make it slightly more "random" by adding some noise to the location that you place the circle inside the grid. This would work really well for sparse placement.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.