Fonctionnement de l’outil Trier
L’outil Trier permet de trier par attributs et caractéristiques spatiales. Le tri spatial permet d’optimiser les opérations spatiales ou géométriques.
Pour trier des entités spatialement (par localisation), spécifiez le champ de géométrie en entrée (il se nomme généralement Shape) à l’aide du paramètre Fields(s) (Champ[s]). Le champ Shape active le paramètre Spatial Sort Method (Méthode de tri spatial). Le paramètre Spatial Sort Method (Méthode de tri spatial) prend en charge les options de tri suivantes : Upper left (Supérieur gauche), Upper right (Supérieur droit), Lower left (Inférieur gauche), Lower right (Inférieur droit) et Peano.
Tri spatial
Les options Upper left (Supérieur gauche), Upper right (Supérieur droit), Lower left (Inférieur gauche) et Lower right (Inférieur droit) numérisent les entités comme un traceur ou une imprimante. Si l’option Upper right (Supérieur droit) est sélectionnée, la numérisation commence à l’angle supérieur droit et sélectionne l’entité située en haut en premier. En allant de haut en bas, si plusieurs entités se trouvent sur la même ligne horizontale, elles sont ordonnées de droite à gauche. La numérisation se poursuit vers le bas et vers la gauche jusqu’à atteindre l’angle opposé (dans ce cas, l’angle inférieur gauche). Les entités sont triées dans l’ordre de numérisation ou d’accès (ou dans l’ordre inverse si l’option Descending (Décroissant) est spécifiée).
L’option de tri Upper right (Supérieur droit) peut être illustrée en prenant un ensemble de points uniformément distribués en entrée.
Dans le diagramme ci-dessus, les nombres représentent la séquence triée selon l’option Upper right (Supérieur droit). L’ordre est inversé si l’option Lower left (Inférieur gauche) est spécifiée.
Voici une illustration montrant comment les composants supérieurs et droits du tri fonctionnent ensemble.
Le composant supérieur du tri spatial a priorité sur le composant droit. Le composant droit est pris en considération uniquement lorsque certaines entités se trouvent au même niveau horizontal.
Tri spatial de Peano
L’option Peano utilise l’algorithme de courbe de Peano. L’algorithme visite toutes les localisations d’un voisinage plus petit avant de passer au voisinage suivant. Ainsi, les localisations à proximité sont plus proches le long de la courbe (ou trajectoire). Au lieu de parcourir l’étendue entière, il effectue la recherche dans les plus petits voisins un par un. Une fois la recherche terminée sur une grande surface, elle reprend sur une autre grande surface. Il recommence ensuite à trier à partir du plus petit voisinage au sein de cette grande surface.
Dans le diagramme ci-dessus, les flèches indiquent la séquence de numérisation. L’algorithme numérise chacun des quatre voisinages rectangulaires séparément. Si la surface était plus grande, la recherche se poursuivrait sur un autre jeu de voisinages, et ainsi de suite. Si les points étaient plus denses, la recherche porterait sur un voisinage beaucoup plus petit.
Voici les avantages d’un algorithme de remplissage d’espace :
Il est rapide.
Il ne nécessite aucun calcul des distances entre les localisations.
Il est parallélisable.
L’algorithme a des applications dans les domaines suivants : résolution du problème de délégué commercial, création d’un système de calcul d’itinéraire et contrôle d’un traceur pour dessiner des cartes.