4
$\begingroup$

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.

Improve this question
$\endgroup$
20
  • 1
    $\begingroup$ Do all the circles have the same fixed radius? What about the pivots? $\endgroup$ – orlp Jan 23 '19 at 4:04
  • 1
    $\begingroup$ "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? $\endgroup$ – John L. Jan 23 '19 at 7:11
  • 1
    $\begingroup$ 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. $\endgroup$ – j_random_hacker Jan 23 '19 at 13:30
  • 1
    $\begingroup$ @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. $\endgroup$ – Discrete lizard♦ Jan 24 '19 at 14:29
  • 1
    $\begingroup$ 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. $\endgroup$ – Discrete lizard♦ Jan 24 '19 at 21:34
2
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thank you for the tip. As I see that I have to bruteforce it, I thought of using a physics engine. $\endgroup$ – Jorge Fuentes González Jan 24 '19 at 21:09
  • $\begingroup$ A constrained optimizer would get you the actual optimum, whereas some kind of physics based simulation wouldn't come with any such guarantee (unless you could prove that it works out the same for this problem for some special reason.) $\endgroup$ – Daniel McLaury Jan 24 '19 at 22:36
  • $\begingroup$ By the way, what are you actually using this for? Maybe you could solve a similar but different problem that's easier to solve but just as good for your purposes. $\endgroup$ – Daniel McLaury Jan 24 '19 at 22:38
  • $\begingroup$ I have a board game where people move tokens around by tapping on them. Tokens (pivot points) never overlap other tokens, but can sit next to each other in different positions. The problem is that for mobile phones tokens are a bit small because of the amount of cells the board has, and the tokens can't be bigger than a cell width/height, and I don't want to enable pinch-zoom for my app. I thought about adding bigger "touch areas" for each token, but when tokens sit next to each other, touch areas don't work as expected because they overlap, so I though into displacing them, and here I am :-) $\endgroup$ – Jorge Fuentes González Jan 24 '19 at 22:54
  • $\begingroup$ I don't get the point of a constrained optimizer. I'm not an "algorithms guy", but more a programmer guy. I ended up with this which works pretty well, and can be optimized a bit more actually: jsfiddle.net/26Ls0nvz/3 but if you can show me more about that "optimum" thing you talk about, that would be awesome, as depending on a physics engine for this is a bit weird. Like killing flies with a cannon. $\endgroup$ – Jorge Fuentes González Jan 24 '19 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.