Algorithme de chargement en bloc pour MX-CIF quadtree

Question

Mon application charge une collection de ~ 100k éléments (rectangles) à partir d'un fichier map, puis génère un quadtree MX-CIF en tant qu'index pour la recherche rapide. Le quadtree est construit au démarrage et son contenu ne change pas à l'exécution.

(Dans un des éléments quadtree, MX-CIF sont stockés par le plus petit noeud contenant pleinement ... les deux noeuds internes et feuilles peuvent contenir des objets)

Dans la première passe, je trouve les extensions extérieures des la collection, donc je sais quelle est la taille du nœud racine. Dans la deuxième étape, j'ajoute chaque élément au plus petit nœud qui le contient entièrement. Une fois qu'un nœud passe un certain nombre d'éléments, il est divisé et les enfants sont redistribués entre le nouveau parent et les quatre nœuds enfants.

Étant donné que j'ai tous les éléments à l'avant, comment pourrais-je construire l'arbre plus efficacement?

Answer 1

Avez-vous vraiment besoin d'un arbre MX-CIF? Pour les rectangles, je proposerais d'utiliser un arbre X ou un arbre PH.

Les arbres X sont dérivés des arbres R et ont d'excellents temps d'insertion si vous connaissez l'ensemble des données à l'avance (chargement en masse). Ils ont également de très bonnes performances de requête. Un exemple d'implémentation se trouve ici: XXL Library

Le PH-Tree est un peu plus lent sur le chargement en vrac, mais beaucoup plus rapidement si les objets sont mis à jour/déplacés par la suite. Les performances de la requête Range sont similaires à celles de l'arbre X, mais l'arbre PH est plus rapide lors de l'extraction de petits ensembles de résultats (le coût principal réside dans l'extraction des valeurs). , ...)). Une implémentation de PH-tree est disponible ici: PH-Tree

Avertissement: J'ai été impliqué dans le développement de l'arbre PH.