3

I'm looking for an efficient way to move hundreds of uniform, possibly intersecting squares away from each other, so they no longer intersect. The resulting new positions should be as close as possible to the original coordinates.

Is there such an algorithm?

quano
  • 18,812
  • 25
  • 97
  • 108
  • Never seen anything like that. Maybe reasoning first on the 1D version of the problem could help. Looks like it can be formulated as a linear programming problem (variables being the shifts). But what do you mean by "uniform" ? –  Apr 04 '14 at 08:06
  • See also http://stackoverflow.com/questions/6750377/move-rectangles-so-they-dont-overlap – brainjam Apr 07 '14 at 20:50
  • ... and http://stackoverflow.com/questions/3265986/an-algorithm-to-space-out-overlapping-rectangles – brainjam Apr 07 '14 at 20:54

1 Answers1

3

Introduce the shift variables Xi+, Xi-, Yi-, Yi- and solve the linear problem that minimizes the sum of the variables under constraints that express the non-overlap like (Ui + Xi+) - (Uj - Xj-) >= S, (Vi + Yi+) - (Vj - Yj-) >= S or similar.

If you are not familiar with linear programming, you should read about: http://en.wikipedia.org/wiki/Linear_programming