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 Champ(s). Le champ Shape active le paramètre Méthode de tri spatial. Le paramètre Méthode de tri spatial prend en charge les options de tri suivantes : Supérieur gauche, Supérieur droit, Inférieur gauche, Inférieur droit et Peano.

Tri spatial

Les options Supérieur gauche, Supérieur droit, Inférieur gauche et Inférieur droit numérisent les entités comme un traceur ou une imprimante. Si l’option 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 (ou dans l’ordre inverse si l’option Décroissant est spécifiée) de numérisation ou d’accès.

L’option de tri 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 Supérieur droit. L’ordre est inversé si l’option 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 tous les emplacements 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.