I'd like to implement a variation of a rectangle packing algorithm in C#. In my case the rectangles have a width and height and a "desired" position in a 2D plane (on the screen). They must however not overlap. I want the algorithm to find the positions of the rectangles that minimizes the distances of their desired positions. I am aware that the order in which the rectangles are placed plays a role but I can't even find a performant algorithm for a fixed or random order. Anyone got an idea or references?

More formal definiton of the problem here

CodePudding user response：

Thanks @tiliavirga, I implemented your suggestion and it works quite well. Some notes:

-I made the repulsive force proportional to only the square root of the overlapping area, because otherwise the first few iterations had huge repulsive forces blowing the constellation apart. (On the other hand, it leads to quick termination which could be important, see below)

-I reduced the attractive force over time towards 0, becuase otherwise the alg oscillates in some cases, where overlapping rectangles are pushed away, then in the next iteration pulled together, then pushed away and so on

-The algorithm can take very long, depending on the parameters (1) how quickly the attractive force weakens, (2) how large the motion of the rectangles is in each iteration and (3) the limit of the total overlapping area which can be tolerated, terminating the algorithm. In time critical applications, e.g. in games where this computation is done every frame, these parameters should be adjusted to result in a quick termination with a not so optimal solution.

All in all, a good enough solution for me. Here is my code (python, notebook):

https://drive.google.com/file/d/1Ux58thqeqtj2kqTjGAMvoXeCU2HNsyAu/view?usp=sharing

and an example runthrough: Example

CodePudding user response：

You can use a variational optimization method, such as Simulated Annealing or Gradient Descent.

Maybe it helps to take a quasi-physical view of the problem. Say there are two kinds of forces in action. One is attractive. It pulls a rectangle toward its desired position and is proportional to (xi-x'i)^2 (yi-y'i)^2. The other is repulsive. It pushes any overlapping rectangle away and is proportional to the area of the overlap. In this case, the repulsive force must be much stronger than the attractive to exclude overlaps. The sum of all forces (the potential energy) is the function to minimize. During optimization, the rectangles will move around in small trial steps (random or directional), getting clean away from each other without straying too far from their desired positions. Eventually, they settle down (reach equilibrium) with minimal deviation and no overlaps.