• I have a Main circle, and Other nearby circles.
• All circles are always the same size.
• No two circles may ever overlap.
• I'd like to find out where Potential circles could be placed near the Main circle (more detail below).
• Ideally, I'd like to do this fast (I know, everyone says so - but trust me I really do!).
• I'd like the answer as a general high level description of the algorithm to use.

This might be a duplicate of

• Red circle is the Main circle.
• Black circles are the Other circles placed nearby.
• The centre of each Potential circle should be on the yellow band. It is a relatively narrow range, slightly less wide than the radius of the circle, I'm not interested in any circles whose centre lies outside of this range.
• Gray are the Potential circles I'd like the algorithm to find:
  1. The one in the upper slightly right, is as close to the Main circle as can be. If any of the three Other circles around it moved any closer to its centre, there would be no Potential circle here.
  2. Lower right, as far from the Main circle as allowed. If the two Other circles next to it were any closer to each other, there would be no Potential circle here.
  3. Four Potential circles drawn on the left. There could be a multitude of these, it'd be fine if the algorithm returned just any one of these.
• The teal circle is a bounding box, if a circle's centre lies outside, it has no impact on placing the circles on the yellow band.

Algorithm input: the Main and Other circles. Desired algorithm output for the image above: three or four Potential circles. One upper slightly right, one lower right, and one or two on the left side (I don't mind too much which it is).

What have I tried? Googling! Looking at Stack Overflow. Thinking.

I'm thinking probably the first thing the algorithm should do is to convert the Other circles from (X, Y) coordinates to (angle, distance) from Main and order by angle. Then split the yellow band into some segments, and for each segment, get all the circles that could influence it.

Here I get lost a bit.

Next step, do some math to try to position the circle. For two circles, I can place a circle so that it just touches them. Perhaps when there are N circles, I just do this bit for each of the pairs and see if I'm left with anything? Or just each of the N with the centre? Can I save this as a draft so it ain't all gone while I think about it some more?

[Edit]: I guess a better approach would be to start with like 12 Potential circles around the Main circle, see which ones are illegal and which Other circles are getting in the way, then try nudging the Potential circles so they get out of the Other stones way. We should know exactly how far we need to move the Potential stone and in which direction, based on which Other stone it's overlapping with. Repeat, hopefully avoiding infinite loops but that I can do I think.

CodePudding user response：

This is a nice problem. Let’s focus on one word: potential.

Think about force directed graph layouts, like this one:

https://observablehq.com/@d3/temporal-force-directed-graph

Eventually, the layout converges on a minimum energy solution, where the spring lengths are minimal.

Let’s bring that to your problem. We will define a potential field. The main and other circles provide repulsive forces. The yellow ring provides an attractive force.

Choose a random point on the plane. Determine if it is feasible, and reject it if not, for example, it overlaps with main or other circle. Now we are left with a circle in a feasible, but non-optimal location. We will move this circle to new candidate positions over several time steps. Sum up the attractive and repulsive forces operating on it, and move it a small amount in the indicated direction. At some point, it is likely that it will try to go to an infeasible position, perhaps overlapping with the main circle. At that point we are done, and we output its position as a good result.