Créer un arbre à partir d'une liste de rectangles

Question

Cela peut être une question stupide, mais rien ne vient immédiatement à l'esprit. Étant donné une liste R des rectangles 2D (x, y, w, h) disposés de telle sorte que tout rectangle donné est soit complètement à l'intérieur ou totalement en dehors de tout autre, quel est le moyen le plus efficace pour déterminer le rectangle entourant immédiatement p de chaque rectangle R? Actuellement, je trier R par y puis x, puis passer par chaque paire (a, b) et tester si a est un enfant de b. Non seulement cela n'est pas très efficace, mais cela ne fonctionne pas non plus correctement: j'ai pensé que puisque R est déjà trié, le dernier parent trouvé devrait être celui qui l'entoure immédiatement, mais cela ne semble pas être le cas. Y at-il quelque chose qui ne va pas dans mon raisonnement? Sinon, je posterai du code.

Answer 1

1. Trier par (x+y).
2. A partir du début de la liste triée, saisissez un rectangle Q.
3. Calculez (x+y+w+h) pour ce rectangle.
4. Pour chaque rectangle R de la liste qui suit le rectangle Q, et a x+y for R < = (x+y+w+h) of Q, vérifiez si R est dans les limites de Q. Si c'est le cas, définissez Q comme parent de R, en remplaçant tout parent précédemment défini.
5. Répétez l'opération pour la liste.