Fonctionnement des outils de distance de coût

Disponible avec une licence Spatial Analyst.

Alors que la distance euclidienne est représentée par une ligne droite, à vol d'oiseau (entre des emplacements), la distance de coût explore le mouvement d'un voyageur sur une étendue. Les outils de distance de coût permettent habituellement de générer le chemin de moindre coût, ou couloir, entre une source et une destination.

Exemples de problèmes résolus par l'analyse de distance de coût

• Identifier l'itinéraire le moins coûteux pour construire une route vers une école proposée.
• Connecter les meilleures parcelles d'habitat pour les lynx avec des couloirs de circulation pour la faune sauvage afin de permettre aux espèces de circuler entre les parcelles.
• Localiser un nouveau pipeline pour connecter des champs pétrolifères à une raffinerie.
• Déterminer le moyen le plus rapide d'atteindre un randonneur blessé à un endroit isolé.
• Déplacer un tank militaire à destination d'un objectif distant lequel doit traverser une région sans réseau routier.

Formule générale pour l'analyse de coût

Le coût du déplacement d'une cellule vers une autre est déterminé par les facteurs suivants :

1. Les caractéristiques de surface (surface de coût).
2. Les caractéristiques du moyen de déplacement. Il peut s'agir du mode de déplacement, notamment à pied, en VTT, etc.
3. Les caractéristiques du mouvement lors du déplacement d'une cellule vers une autre, à savoir en montée ou en pente, par exemple.

La formule générale de distance de coût est la suivante :

Cost = Cost of travel  *  Characteristics  *  Movement characteristics       over surface       of the mover        on the surface

Les outils de distance de coût tiennent compte des caractéristiques de la surface et de la surface de coût, qui est expliquée ci-dessous. Reportez-vous à la rubrique Impact des caractéristiques de la source sur l'analyse de distance de coût pour savoir comment contrôler les caractéristiques du moyen de déplacement dans les outils relatifs à la distance. L'outil Distance de chemin vous permet de définir les caractéristiques du mouvement d'une cellule à une autre à l'aide d'un raster de surface et de facteurs horizontaux et verticaux.

Distance de coût et Connectivité de coût

L'outil Connectivité de coût permet de créer un réseau optimal de chemins entre une série de régions en entrée. La séquence d'outils Distance de coût et Chemin de coût permet de créer des chemins entre des sources et des destinations identifiées. Toutefois, la séquence des deux outils permet parfois de créer un réseau de chemins en isolant de manière itérative une région en tant que source et en la connectant aux autres régions identifiées comme des destinations. Ce processus est renouvelé pour chaque région et les chemins de moindre coût résultants sont combinés.

Voici les limites de cette approche itérative :

• En connectant toutes les régions entre elles, vous générez un nombre infaisable de chemins, et particulièrement en présence de nombreuses régions. Le réseau résultant ignore également l'approche progressive visant à établir une connectivité. Cela signifie que pour atteindre une région distante, vous pouvez utiliser plusieurs chemins connectant une séquence de régions vous séparant de la région distante.
• Dans bien des cas, pour limiter le nombre de chemins combinés, les deux régions les plus proches sont connectées. La distance euclidienne permet d'identifier la source et la destination. Toutefois, deux régions peuvent être proches l'une de l'autre, mais il peut être très coûteux de les traverser, car le relief présente des montagnes ou des rivières. Il est ainsi plus avantageux de connecter des régions en fonction de la proximité de coût, comme c'est le cas dans l'outil Connectivité de coût.

  

  Même si les régions A et B sont proches en termes de distance euclidienne, elles sont éloignées en termes de distance de coût, en raison des montagnes qui les séparent.

• Souvent, différents chemins dans différentes régions se rejoignent pour suivre la même direction à destination d'une région commune (en suivant le même chemin de moindre coût sur une partie du trajet). Il est difficile de gérer et d'analyser la portion partagée de ces chemins de raster. Ainsi, lors des analyses ultérieures, il est préférable de traiter chaque chemin comme une entité distincte.
• Les chemins créés par l'outil Chemin de coût n'atteignent que le tronçon d'une région surfacique et un emplacement sur une ligne dans le cas des régions linéaires. Ainsi, les chemins individuels ne sont pas connectés et aucun réseau n'est créé.

Calcul d’une 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.

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 plusieurs liens.

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 de 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ù

  cost1 : coût de la cellule 1

  cost2 : 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ù

  cost2 : coût de la cellule 2

  cost3 : coût de la cellule 3

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

  accum_cost : 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.

Les 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é, 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é précédemment dans la cellule à la ligne 3, colonne 1, 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 distance de coût cumulé, ou pondéré. La procédure utilisée garantit que le coût cumulé le plus faible est garanti pour 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 plus faible coût cumulé 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 en sortie de distance de coût