Algorithm for finding an empty space that fits a rectangle that is closest to a target rectangle among other rectangles

Question

Let's say you're placing rectangular tooltips on a screen of elements you want to provide information for. You want all these tooltips to be visible all at once and not cover any of the nodes any of the other tooltips are for.

You want each tooltip to be as close to the item its related to as feasible. What algorithm(s) exist to help solve this problem?

I've checked out rtrees, which seem to only help you find collisions, but don't help on the front of actually searching for free locations. I've found rectangle packing algorithms that search for a position unconstrained by a maximization function (like "be closest to this other element as possible").

I can imagine an algorithm that has some physics simulation where nodes and their tooltips are each connected by some kind of rubber band and plays it out until equilibrium, but I'd think that things could be calculated faster and less complicated than that.

Any related algorithms or libraries would be helpful. Bonus points for a javascript library : )

Answer 1

You might investigate map labeling algorithms. See, for example, these lecture notes by Robero Tamassia @Brown: PDF download.

---