L’objectif du projet est d’écrire un algorithme permettant de retrouver toutes les villes comprises dans
un carreau rectangulaire délimité par les points de latitude et longitude (φ1, λ1),(φ2, λ1),(φ1, λ2),(φ2, λ2).
Pour ce faire nous nous proposons d’étudier les trois approches suivantes :
Un arbre binaire de recherche La première approche, la plus simple, consiste à stocker les villes en
utilisant une des coordonnée comme clé (par exemple la latitude). Il s’agirait donc de :
1. Rechercher Sφ, l’ensemble des villes comprises entre deux latitudes ;
2. Filtrer Sφ pour ne garder que les villes comprises entre deux longitudes S.
Deux arbres binaires de recherche La seconde approche, consiste à stocker les villes dans deux
arbres binaires de recherche. Le premier admet comme cl ́e les latitudes des villes et le second leur
longitude. Il s’agira donc de
1. Rechercher Sφ, toutes les villes comprises entre deux latitudes ;
2. Rechercher Sλ, toutes les villes comprises entre deux longitudes ;
3. Calculer l’intersection de ces deux ensembles : S = Sφ ∩ Sλ.
Un arbre binaire de recherche avec Z-score La troisième approche repose sur un seul arbre de
recherche qui utilise comme clé une combinaison de la latitude et de la longitude k = Z(φ, λ) qui
garantit que Z(φm, λm) ≤ Z(φ, λ) ≤ Z(φM, λM) pour φm ≤ φ ≤ φM ∧ λm ≤ λ ≤ λM. On peut alors
retrouver les villes de la mani`ere suivante :
1. On recherche SZ, toutes les villes dont les clés sont comprises entre Z(φm, λm) et Z(φM, λM) oú
φm = min{φ1, φ2}, λm = min{λ1, λ2}, φM = max{φ1, φ2} et λM = max{λ1, λ2}.
2. On filtre SZ pour ne garder que l’ensemble S des bonnes villes.
On utilisera le code de Morton comme fonction Z. Celui-ci consiste à entrelacer les bits des coordonnées.
Bonjour! D'abbord je dois dire que votre tache n'est pas bien formulee. Avez-vous besoin de l'algorithm ou bien du code ecrit en c++? S'il s'agit de l'algorithm je dois demander dans quelle forme vous voulez avoir cet algorithm ecrit? Car il y a plusieurs formats pour representer des algorithms. Aussi dois-je m'enqueter de comment detaille la description doit etre. je veux savoir s'il faut decrire l'algorithm de la construction d'arbres binaires? :)