Fonctionnement des outils de distance de coût

Tous ces outils utilisent essentiellement le même algorithme pour calculer la sortie. La différence repose essentiellement sur la sortie principale de chaque outil.

Calcul d’une distance de coût

L’outil Distance de coût permet de créer un raster en sortie dans lequel chacune des cellules se voit attribuer le coût cumulé du déplacement jusqu'à la cellule source la plus proche. L'algorithme utilise la représentation d’une cellule nœud/lien employée dans la théorie des graphes . Dans la représentation nœud/lien, le centre de chaque cellule est interprété comme un nœud et chaque nœud est connecté à ses nœuds adjacents par des liens multiples.

Chacun des liens est associé à une impédance. L'impédance est dérivée des coûts associés aux cellules situées à chaque extrémité du lien (à partir de la surface de coût) et de la direction du mouvement dans les cellules.

Le coût attribué à chacune des cellules représente le coût par unité de distance pour le déplacement à travers chaque cellule. La dernière valeur par cellule est la taille de cellule multipliée par la valeur du coût. Par exemple, si le raster de coût a une taille de cellule de 30 et qu’une cellule déterminée a une valeur de coût de 10, le dernier coût de cette cellule est de 300 unités.

Coûts de déplacement liés aux nœuds

Le coût du déplacement d’un noeud à l’autre dépend de l’orientation des noeuds dans l’espace. La relation entre les cellules a également une incidence sur le coût de déplacement.

Coût du nœud adjacent

Lors d'un déplacement entre une cellule et l'une des quatre cellules voisines directement connectées, le coût de déplacement à travers les liens jusqu'au nœud voisin est le coût de la cellule 1 plus le coût de la cellule 2, divisé par 2 :

 a1 = (cost1 + cost2) / 2

• où :

  coût1 : coût de la cellule 1

  coût2 : coût de la cellule 2

  a1 : coût total du lien entre la cellule 1 et la cellule 2

Coût perpendiculaire cumulé

Le coût cumulé est déterminé par la formule suivante :

 accum_cost = a1 + (cost2 + cost3) / 2

• où :

  coût2 : coût de la cellule 2

  coût3 : coût de la cellule 3

  a2 : coût du déplacement entre les cellules 2 et 3

  coût_cumul : coût cumulé pour passer à la cellule 3 depuis la cellule 1

Coût de nœud en diagonale

Si le mouvement est diagonal, le coût de déplacement à travers le lien est 1,414214 (soit la racine carrée de deux) multiplié par le coût de la cellule 1 plus le coût de la cellule 2, divisé par 2 :

 a1 = 1.414214 (cost3 + cost2) / 2

Lorsque vous déterminez le coût cumulé d'un mouvement diagonal, la formule suivante doit être utilisée :

 accum_cost = a1 + 1.414214(cost2 + cost3) / 2

Liste des cellules de coût cumulé

La création d'un raster de distance de coût cumulé à l'aide de la théorie des graphes est une façon d'identifier la cellule de plus faible coût et de l'ajouter à une liste en sortie. Il s'agit d'un processus itératif qui s'applique d'abord aux cellules source. Chaque cellule a pour objectif d'être attribuée rapidement à un raster de distance de coût en sortie.

Dans la première itération, les cellules source sont identifiées et associées à la valeur zéro étant donné qu'il n'y a aucun coût cumulé à leur renvoyer. Ensuite, tous les voisins de la cellule source sont activés et un coût est attribué aux liens entre les nœuds de la cellule source et les nœuds des cellules voisines, à l'aide des formules de coût cumulé ci-dessus. Chacune des cellules voisines pouvant atteindre une source, elle peut être sélectionnée ou attribuée au raster de coût cumulé en sortie. Pour être attribuée au raster en sortie, une cellule doit avoir le deuxième chemin de plus faible coût menant à une source.

Ces valeurs de coût cumulé sont triées dans une liste, du coût cumulé le plus faible au plus élevé.

La cellule de plus faible coût est sélectionnée dans la liste des cellules de coût cumulé actives, et la valeur de cet emplacement de cellule est attribuée au raster de distance de coût en sortie. La liste des cellules actives se développe de manière à inclure les voisins de la cellule sélectionnée, dans la mesure où ces cellules ont à présent un moyen de parvenir à une source. Seules les cellules capables d'atteindre une source sont actives dans la liste. Le coût associé au déplacement jusqu'à ces cellules est calculé à l'aide des formules de coût cumulé.

Là aussi, la cellule active de la liste ayant le coût le plus faible est sélectionnée, les cellules voisines sont développées, les nouveaux coûts sont calculés et les nouvelles cellules de coût sont ajoutées à la liste active.

Il n'est pas nécessaire de connecter les cellules source. Toutes les sources déconnectées contribuent à part égale à la liste active. Seule la cellule ayant le coût cumulé le plus faible est sélectionnée et développée, indépendamment de la source à laquelle elle sera allouée.

Ce processus d'allocation se poursuit. De plus, les cellules de la liste active sont mises à jour si un nouvel itinéraire plus avantageux est créé suite à l'ajout de nouveaux emplacements de cellule au raster en sortie.

Cette mise à jour peut se produire suite à l'introduction de nouveaux itinéraires pour les cellules de la liste active, à mesure que davantage de cellules sont allouées au raster en sortie. Lorsque la cellule ayant la valeur la plus faible dans la liste des coûts cumulés est allouée au raster en sortie, tous les coûts cumulés sont calculés. Ces coûts sont également calculés pour les cellules voisines de la cellule en sortie qui vient d'être attribuée, même si les cellules voisines font partie de la liste active par l'intermédiaire d'une autre cellule. Si le nouveau coût cumulé des emplacements de la liste active est supérieur au coût cumulé actuel des cellules, la valeur est ignorée. Si le coût cumulé est inférieur, l'ancien coût cumulé de l'emplacement est remplacé dans la liste active par la nouvelle valeur. La cellule qui trouve un itinéraire plus avantageux et préférable vers une source remonte dans la liste active sélectionnée.

Dans l'exemple ci-dessous, l'emplacement de cellule à la ligne 3, colonne 1 (mis en évidence par le cadre), avait un coût cumulé égal à 11 lorsqu'il a été placé dans la liste active pour parvenir à la source située en premier dans le raster. Cependant, dans la mesure où la source située en dessous s'est étendue jusqu'à cet emplacement, la cellule a découvert un itinéraire de coût cumulé plus avantageux pour atteindre une source. La valeur de l'emplacement a été mise à jour dans la liste active et allouée à la sortie précédente, en raison de ce coût cumulé plus faible.

S'il y a plusieurs zones ou ensembles déconnectés de cellules source dans le raster de sources en entrée, le processus d'expansion se poursuit et alloue la cellule de plus faible coût de la liste active, indépendamment de sa source.

Lorsque les fronts d'expansion se rencontrent, le chemin de plus faible coût amenant à la source est utilisé jusqu'à ce que les toutes cellules candidates aient reçu une valeur de coût.

Il est concevable que lorsque les structures d'expansion se rencontrent, les cellules d'une structure découvrent qu'elles peuvent parvenir à la cellule source d'un autre ensemble ou d'une autre structure d'expansion à un coût plus avantageux. Si tel est le cas, elles sont réattribuées à la nouvelle source. Ce comportement a été observé dans la cellule à la ligne 3, colonne 1 précédemment, mais il est également illustré ci-dessous par la cellule positionnée à la ligne 3, colonne 6.

Lorsque toutes les cellules ont été sélectionnées dans la liste active, le résultat est un raster de coût cumulé ou de distance pondérée. La procédure utilisée garantit que le coût cumulé le plus faible est appliqué à chacune des cellules. Ce processus se poursuit pour toutes les cellules jusqu'à ce que le tronçon du raster soit rencontré, la limite de la fenêtre trouvée ou la distance maximale atteinte.

Aucun déplacement n'est autorisé à travers les cellules contenant des valeurs NoData. Le chemin de plus faible coût des cellules à l'arrière d'un groupe de cellules NoData est déterminé par le coût de déplacement autour de ces emplacements. Si un emplacement de cellule est associé à la valeur NoData dans le raster de coût en entrée, cette valeur est attribuée à l'emplacement de cellule dans le raster en sortie de distance de coût.

Valeurs d’une distance de coût en sortie