Fonctionnement des outils de calcul du chemin de distance

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 chemin permet d’analyser une distance de coût relative à des facteurs horizontaux et verticaux, ainsi que la distance réelle d’une surface. L'outil Allocation de distance de chemin emploie le même algorithme, mais le résultat est un raster qui désigne la source la plus proche pour chaque cellule et chaque emplacement. L'outil Antécédence de distance de chemin identifie la direction du voisin qui est la prochaine cellule sur le chemin de coût le moins cumulé par rapport à la source la plus proche.

Calcul d’une distance de chemin

Les outils de calcul des distances de chemin créent un raster en sortie dans lequel chacune des cellules se voit attribuer le coût cumulé depuis la cellule source de plus faible coût. L'algorithme utilise la représentation de cellule nœud/lien. Dans cette représentation, le centre d'une cellule est interprété comme un nœud, et chaque nœud est connecté à ses nœuds adjacents par des 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.

Pour simplifier la discussion, les formules suivantes identifient comment le coût de déplacement est cumulé entre les cellules sur la surface de coût uniquement ; la modification du coût en intégrant la distance entre les surfaces et les facteurs horizontaux et verticaux sera traitée dans une prochaine section.

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 correspond au coût du déplacement dans la cellule 1.

  coût2 représente le coût de déplacement à travers la cellule 2.

  a1 représente le coût attribué au lien de la cellule 1 à 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 représente le coût de déplacement à travers la cellule 2.

  coût3 représente le coût de déplacement à travers la cellule 3.

  coût_cumul représente le coût cumulé de déplacement vers la cellule 3 depuis la cellule 1.

  Remarque : dans l’illustration ci-dessous, a2 désigne le coût d’un déplacement de la cellule 2 à la cellule 3.

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 déplacement à travers la cellule 1, plus le coût de déplacement à travers la cellule 2, divisé par 2 :

 a1 = 1.414214(cost1 + cost2) / 2

Lorsque vous déterminez le coût cumulé d'un mouvement diagonal, la formule suivante est 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.

Comparaison d’une distance de chemin et d’une distance de coût

Le traitement effectué avec l’outil Distance de chemin est similaire à celui que vous effectuez avec l’outil Distance de coût (reportez-vous à la rubrique Fonctionnement des outils de distance de coût). D'abord, les cellules source sont identifiées. Ensuite, le coût du déplacement vers chaque voisin adjacent à une cellule source est déterminé. Puis, chacune des cellules voisines est classée de la moins coûteuse à la plus coûteuse. L'emplacement de cellule la moins coûteuse est supprimé de la liste. Enfin, le coût cumulé le plus faible de déplacement vers chacun des voisins de la cellule supprimée dans la liste est déterminé.

Le processus est répété jusqu'à ce que toutes les cellules du raster se voient attribuer un coût cumulé. La différence entre les outils Distance de coût et Distance de chemin réside dans la manière dont le coût de déplacement d'une cellule vers une autre est calculé.

Formule pour calculer une distance de chemin

Dans le cas d’une cellule, les outils de calcul d’une distance de chemin doivent permettre de définir le chemin le plus rentable pour chaque emplacement et de se rapprocher de la cellule issue de la source la moins onéreuse. Pour chaque cellule, vous devez identifier le chemin de coût le plus rentable par rapport à une source, cette source proprement dite et le chemin de moindre coût.

Distance de chemin

Le coût de déplacement entre les cellules sur la surface de coût est déterminé par les formules décrites ci-dessus. Dans l'outil Distance de chemin, ces coûts (identifiés par Cost_Surface dans les équations ci-dessous) peuvent être modifiés par la distance de surface (Surface_distance) et les facteurs horizontaux et verticaux. La formule employée pour calculer le coût total d’un déplacement d’une cellule a vers une cellule b est fonction de la direction qu’emprunte le chemin de moindre coût par rapport à une cellule adjacente dans une direction perpendiculaire ou diagonale :

• Perpendiculaire :

  Cost_distance = Cost_Surface(ab) * Surface_distance(ab) *
                   {[Friction(a) * Horizontal_factor(a) + 
                     Friction(b) * Horizontal_factor(b)] / 2} *
                   Vertical_factor(ab)

• Diagonale :

  Cost_distance = Cost_Surface(ab) * Surface_distance(ab) * 1.414214 *
                   {[Friction(a) * Horizontal_factor(a) + 
                     Friction(b) * Horizontal_factor(b)] / 2} *
                   Vertical_factor(ab)

Notez bien que la division de la friction des segments par deux est reportée jusqu'à ce que le facteur horizontal soit intégré.

Distance de coût cumulée

Le coût de déplacement cumulé d’une cellule a vers une cellule c en passant par une cellule b est le suivant :

Accum_cost_distance = a1 + Cost_Surface(bc) * Surface_distance(bc) * 
                 {[Friction(b) * Horizontal_factor(b) + 
                   Friction(c) * Horizontal_factor(c)]/2} *
                 Vertical_factor(bc)

• où :

  a1 correspond au coût total du déplacement entre la cellule a et la cellule b.

Paramètres horizontaux et verticaux

Il existe plusieurs types de paramètres que vous pouvez utiliser pour contrôler les facteurs de friction horizontaux et verticaux. Avec chacun de ces facteurs, vous pouvez employer plusieurs modificateurs pour optimiser l’analyse.

Pour plus d'informations sur ces paramètres, passez à la section suivante :

Incidence des facteurs horizontaux et verticaux sur la distance de chemin