1

Given a canvas with a bunch of circles with a certain radius, say 50, how do I place another circle with radius 10 in a random location so that it does not collide or overlap with any existing circles?

I know I can place the circle and then check if there are any collisions and retry, however I will need to place a lot of circles and this could get stuck. Was wondering if there are any better ways to solves this.

TaoPR
  • 5,932
  • 3
  • 25
  • 35
user3130915
  • 11
  • 2
  • 1
    Hello and welcome to Stackoverflow. Could you show us some of the code you have tried to get working until now? – plocks Jun 01 '15 at 04:20
  • The basic approach is to position it - then detect collisions (using basic circle-circle collision detection). If there are collisions, place it somewhere else. Repeat. (If after an excessive number failures; abort and/or restart the process.) – user2864740 Jun 01 '15 at 04:23
  • 1
    This will be used for a simulation and there might be a lot of collisions so I was just wondering in there is anything better then testing random points until a point succeeds. – user3130915 Jun 01 '15 at 04:27
  • @user3130915 - If you 'pre-mapped' a grid of potential circle positions, you could put the positions in an array, and randomly pull them out and use them. But the circle positions would be limited to the ones you store. – Steve Wellens Jun 01 '15 at 04:31
  • How would I go about creating a grid of potential positions without trying every pixel on the canvas. – user3130915 Jun 01 '15 at 04:35
  • @user3130915 You *don't* try every pixel. You use 2d math for the *logical circles*. You only have to compute the logical bounds. For 50 circles even the basic method may very well "OK" - that is, unless it's the limiting bottleneck, Just Don't Worry About It. If you're interested in *packing algorithms* then search for those (which are less interested in 'being random'). – user2864740 Jun 01 '15 at 05:09

1 Answers1

0

The solution that an going to use is to create another image with the same size and then render every circle onto that image but with a new radius that equals the existing circles radius plus then one I want to to place. Then every pixel that is free of a circle is a possible location and I can pick from those locations.

user3130915
  • 11
  • 2