Comment utiliser un arbre pour organiser des éléments HTML afin de réduire le nombre de vérifications de chevauchement?

Question

J'ai un certain nombre d'éléments que j'ai besoin d'ajouter à une page en utilisant javascript avec des données tirées du serveur avec leurs informations de position. Je veux les arranger pour qu'il n'y ait pas de chevauchement. Par exemple, element 5 serait déplacé à l'endroit où se trouve la boîte verte fine, de sorte qu'elle ne chevauche pas element 3.

J'ai réussi à créer une fonction qui décide si deux boîtes se chevauchent. Par exemple, si je cours overlaps($('#element5')[0],$('#element3')[0]), il retournera true. Cependant, avec cette fonction, je devrais parcourir chaque élément et le comparer avec tous les autres éléments. Donc, pour 50 éléments, je devrais faire exécuter la fonction overlays 1275 fois, ce qui prendrait beaucoup de temps à charger. J'ai décidé que je ferais mieux de créer un arbre pour organiser les éléments en premier afin que je puisse facilement déterminer les 2 éléments dont j'aurais besoin pour exécuter la fonction de superposition, réduisant considérablement le nombre d'exécutions de la fonction de superposition. Cependant, je suis extrêmement confus sur la façon dont cela fonctionnerait. Comment pourrais-je les organiser de sorte que je n'aurais qu'à exécuter la fonction avec un petit nombre? Deux des limites de l'arbre ne se chevaucheraient-elles pas et rendraient cette technique redondante? Quelle serait la meilleure façon de faire cela?

Answer 1

Dans un R-tree, pages rectangulaire peut en effet se chevauchent.

Lors de la recherche de chevauchements, vous devrez alors explorer les deux groupes.

Mais le nombre de pages qui se chevauchent dans l'arborescence ne devrait pas être trop grand (à moins que l'arbre ait été construit très mal), donc cela donnera une bonne accélération. En supposant que vous avez 50 éléments dans 5 pages de 10 éléments chacun, vous devrez d'abord tester les 5 pages de niveau supérieur, puis peut-être tester les 10 éléments dans 0-2 de ces pages, donc peut-être 15 chevaucher les tests au lieu de 50. Les nombres exacts varieront naturellement beaucoup.

Pour une solution HTML, cependant, je considérerais plutôt une approximation basée sur une grille. Divisez votre surface en 10x10 cellules. Chaque cellule contient des références des rectangles qui se chevauchent avec cette cellule de grille.

Lors du test de chevauchement, vous examinez les cellules de la grille que le rectangle de la requête touche, collectez tous les rectangles existants référencés, puis vous ne testez que ceux qui se chevauchent. Si vous stockez deux listes dans chaque cellule - "chevauche partiellement" et "chevauche complètement", vous pouvez même ignorer de nombreux tests de chevauchement: si une cellule de grille touchée par l'une est complètement recoupée par l'autre, elle se chevauchera quelque part. Une autre approche consisterait à trier les rectangles par axe X, afin de réduire rapidement le nombre de rectangles qui peuvent effectivement chevaucher une recherche binaire. Cela devrait également réduire considérablement le nombre d'appels d'intersection. Oh, et surtout: 1275 tests de chevauchement ne devraient pas prendre beaucoup de temps de toute façon. C'est en quelque sorte un petit ensemble de données dont vous parlez. R-arbres et approches similaires sont destinés à des ensembles de données avec des millions d'éléments.