patternMinor
Algorithm to separate circles to reduce collision the maximum between them
Viewed 0 times
themaximumcollisionseparatecirclesalgorithmreducebetweenthem
Problem
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
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
Solution
If you want to brute force it, this is a constrained optimization problem where the quantity you're minimizing is the overlap area, the variables are the x and y coordinates of each circle's center, and the constraints are that each center lies within a red circle.
Depending on how you want to count areas inside three or more circles, the formula for the overlap arra can be reasonably simple or a huge mess that gets worse with the number of circles.
Depending on how you want to count areas inside three or more circles, the formula for the overlap arra can be reasonably simple or a huge mess that gets worse with the number of circles.
Context
StackExchange Computer Science Q#103264, answer score: 2
Revisions (0)
No revisions yet.