Algorithme pour trouver un espace vide qui correspond à un rectangle qui est le plus proche d'un rectangle cible parmi les autres rectangles

Question

Disons que vous placez des info-bulles rectangulaires sur un écran d'éléments pour lesquels vous voulez fournir des informations. Vous voulez que toutes ces infobulles soient visibles en une seule fois et ne recouvrent aucun des noeuds auxquels les autres infobulles sont destinées.

Vous souhaitez que chaque info-bulle soit aussi proche que possible de l'élément concerné. Quel (s) algorithme (s) existe-t-il pour aider à résoudre ce problème?

J'ai vérifié rtrees, qui semble seulement vous aider à trouver des collisions, mais n'aide pas sur le front de la recherche d'emplacements libres. J'ai trouvé des algorithmes de compression de rectangle qui recherchent une position non contrainte par une fonction de maximisation (comme "être le plus proche possible de cet autre élément"). Je peux imaginer un algorithme qui a une simulation de physique où les nœuds et leurs infobulles sont reliés par une sorte de bande de caoutchouc et joue jusqu'à l'équilibre, mais je pense que les choses pourraient être calculées plus rapidement et moins compliquées que cette. Tous les algorithmes ou bibliothèques connexes seraient utiles.

Points bonus pour une bibliothèque javascript:)

Answer 1

Vous pouvez effectuer une recherche map labeling algorithms. Voir, par exemple, ces notes de cours par Robero Tamassia @ Brown: PDF download.

---