Position elements without overlap

Question

I have a number of rectangular elements that I want to position in a 2D space. I calculate an ideal position for each element. Now my problem is that many elements overlap as very often the ideal positions are concentrated in one region. I want to avoid overlap as much as possible (doesn't have to be perfect, though). How can I do this?

I've heard physics simulations are suitable for this - is that correct? And can anyone provide an example/tutorial?

By the way: I'm using XNA, if you know any .NET library that does exactly this job - tell me!

Answer 1

Box2D is a widly used (free) physics library that can achieve the needed task: Link

Answer 2

One way the physics engine can be used:

Put positive electric charges (or some kind of repulsive force) on each rectangles and simulate the forces and movements. Also, as Eyal was kind enough to point out, you also need some attractive forces to keep them from drifting away. This can be modelled by springs (again as Eyal points out). They will hopefully end up in some sort of equilibrium which might involve non-overlapping rectangles.

I believe similar ideas (force based heuristics) are used in determining nice looking layouts of graphs (the nodes and edges one).

Disclaimer: I haven't used this myself.

Hope that helps!

Answer 3

The algorithm that you are looking for is linear interpolation. XNA has its own lerp function.