# Algorithm to separate circles to reduce collision the maximum between them

I'll try to do my best to explain this.

I have X circles (from 2 to 4) which can move around smaller pivot circles. The pivot circles are fixed and cannot be moved once they are in the "field". Pivot circles are never created colliding with other pivot circles. Something like this:

Red are pivot circles (fixed) and orange are the normal circles (displace without exiting the pivot circles).

Now if I put two pivot circles near, the algorithm should do something like this:

This is pretty easy to achieve. Detect colliding circles and displace them the needed amount. Because red circles never collide, the orange circles are never going to break the "do not exit the pivot circle" rule.

The problem comes when 3 or more circles come into play. Because they cannot exit the pivot circle zone, so there should be some vertical/horizontal movement, like this:

I think this is the least colliding I can achieve when 4 pivots are next to the other. I created this manually but I'd like to know if there's already an algorithm to detect this efficiently without making a lot of detections/passes to achieve the least colliding factor, as I don't like everything that I'm thinking on.

The best I can think of is to simply do a loop where I detect all circle collisions, then displace the circles the amount needed for them to avoid the collisions the maximum possible, then repeat the loop, and repeat until I find that the "collision factor" is not reduced anymore for the next X steps. To make the circles go "up" and "down" I can try to create a bit of noise each time, and the algorithm will do the rest to move the circles up and down. Also, instead of noise I can try to detect if they are colliding "horizontally" or "vertically" and add a bit of horizontal/vertical movement when a circle with 2 or more collisions has a perfect horizontal/vertical collision.

I don't like this much actually, so well, here I am hehe.

I can't think of something, but I'm pretty sure that there's something that can be calculated with one step, instead of looping the same step multiple times, but I'm really stuck and nothing comes out of my head.

• Do all the circles have the same fixed radius? What about the pivots?
– orlp
Jan 23, 2019 at 4:04
• "Reduce collision the maximum between them". Do you want to reduce the area of all overlapped regions? Or just the number of pairs of colliding circles? Or what? Jan 23, 2019 at 7:11
• This looks a lot like the problem of placing labels on a map. For some variants, when a totally overlap-free solution exists, it can be found in polynomial time using 2SAT; if no totally overlap-free solution exists, you may need to go to MAX-2SAT, which is NP-hard, but can actually be solved to within about 6% of optimal in poly-time. Jan 23, 2019 at 13:30
• @j_random_hacker To add, I think that we can transform this problem a bit and see that it is harder than point labeling 4-location placement model, which known to be NP-hard. Also see Wikipedia on labeling. Jan 24, 2019 at 14:29
• If you have found some solution that serves your needs, feel free to self-answer your question with an overview of your solution. This can help others that have similar problems as yours. Jan 24, 2019 at 21:34