Algorithme d’accumulation de distance

Disponible avec une licence Spatial Analyst.

Les outils Accumulation de distance et Allocation de distance remplacent les anciens outils de distance de coût. Ces nouveaux outils mesurent la distance de coût dans toutes les directions en reconstruisant une surface cumulée continue au lieu de rechercher les chemins dans un réseau de centres de cellules. Vous pouvez créer des surfaces de coût cumulé en sortie à partir de surfaces de coût de friction en entrée et d’autres paramètres. Comme pour d’autres surfaces, vous pouvez comprendre plus précisément les résultats en ajoutant des isolignes (lignes de coût cumulé identique), en les visualisant en 3D et en les visualisant en les associant à des bassins versant d’allocation. De manière générale, la construction d’une telle surface a pour finalité de tracer les chemins de moindre coût, qui sont les chemins dont la pente est la plus forte.

Surface de coût cumulé

L’algorithme utilisé par ces outils reconstruit une surface à partir de sa pente. Cette approche donne de meilleurs résultats qu’une approche utilisant un réseau basé sur les centres de cellules.

Ancienne approche des chemins de réseau

Dans les anciens outils de distance de coût (Allocation de coût, Antécédence de coût, Distance de coût, Distance de chemin, Allocation de distance de chemin et Antécédence de distance de chemin), les valeurs de cellule du raster de coût en entrée sont associées par paires et les résultats sont affectés sous forme de poids d’arêtes dans un réseau connecté par les centres de cellule. Pour plus d’informations, consultez les rubriques Fonctionnement des outils de distance de coût et Fonctionnement des outils de distance de chemin. Un algorithme de chemin le plus court en réseau utilise ces poids d’arêtes pour trouver le chemin de plus faible coût cumulé sur le réseau partant de chaque source jusqu’à chaque cellule dans la zone d’analyse. La longueur pondérée de ce chemin de réseau est enregistrée comme le plus faible coût cumulé pour chaque cellule non source.

Dans cette approche, les chemins les plus courts en ligne droite sont introuvables. Par exemple, dans la figure ci-dessous, avec tous les poids d’arêtes égaux à 1, le chemin de réseau le plus court est A-B’-B et non AB.

Figure 1. Le chemin le plus court en ligne droite de A à B (ligne bleue) n’est pas découvert par un ancien outil de distance de coût. On utilise au contraire A-B’-B comme le chemin le plus court (ligne orange), car on peut seulement se déplacer dans huit directions à partir du centre de la cellule vers le centre de la cellule adjacente.

Ce billet de blog inclut un exemple géographique d’une distorsion de réseau.

Approche de reconstruction de la surface

Avec les outils Accumulation de distance et Allocation de distance, rechercher le plus faible coût cumulé ne relève plus d’un réseau. Le raster de coût cumulé en sortie est une surface de forme inconnue. Vous voulez découvrir cette forme en considérant seulement sa pente au niveau de chaque cellule de la zone d’étude. Cette approche fait appel aux concepts de la géométrie différentielle pour éliminer le problème de direction dans 8 sens et calcule la distance véritable ainsi que les coûts dans toutes les directions.

La surface de coût cumulé répond à trois questions importantes :

• Où le coût augmente rapidement sous forme d’une fonction de distance ?
• Quelles sont les cellules source les plus proches d’une cellule non source donnée ?
• Quel chemin doit être emprunté depuis une cellule non source pour parvenir à la cellule source la plus proche ?

Vous pouvez utiliser des vues 3D et des isolignes avec la surface en sortie pour répondre à ces questions. Vous pouvez utiliser les outils Allocation de distance et Chemin optimal comme ligne pour obtenir des réponses plus précises.

Les paragraphes ci-dessous décrivent la relation entre une surface de coût de friction simple en entrée et la surface de coût cumulé en sortie.

Surface simple de coût de friction en entrée

Considérons un raster de coût de friction simple avec une section centrale de coût = 3, une section médiane de coût = 2 et une section extérieure de coût = 1.

Un raster de coût de friction en entrée sous forme d’anneaux concentriques avec un point signalant le centre est illustré.

L’interprétation 3D permet de comprendre la relation entre le raster de coût de friction et la surface de coût cumulé en sortie. La hauteur h de la surface au niveau de la cellule c est la somme des pentes à partir du raster de coût en entrée multiplié par les distances sur lesquelles ces pentes sont actives (h = 3 * d1 + 2 * d2 + 1 * d3).

La relation entre le coût de friction en entrée et la surface de coût cumulé en sortie est illustrée sous forme d’une représentation 3D.

Une vue dans le plan de la même surface en sortie montre la façon dont les isolignes illustrent le changement de coût cumulé. Les valeurs de pente et d’exposition au niveau de l’emplacement de la cellule c sont également affichées. L’exposition (direction de plus forte pente) se trouve toujours à angle droit de l’isoligne.

Les isolignes illustrent la façon dont le coût cumulé change dans une vue dans le plan de la surface raster.

Incorporer le plus faible coût cumulé

Un cas légèrement plus complexe est illustré ci-dessous. Le coût cumulé (élévation) au niveau d’une cellule non source provient de la source parvenant à cette cellule avec le coût le plus faible.

Le raster de coût a deux valeurs : 1 en gris clair et 3 en gris foncé. Les points source sont S1 et S2. La cellule non source D est plus proche de S1 en termes de coût cumulé.

Les points source en entrée et une cellule source sont superposés à un raster de coût en entrée.

Ajouter des isolignes à la surface de coût cumulé vous aide à visualiser la vitesse à laquelle le coût change lorsque vous vous éloignez des sources. En partant d’un emplacement non source et en vous déplaçant à angle droit en direction des isolignes, vous revenez vers la cellule source la plus proche. Le chemin ne rejoint pas la source la plus proche d’un point de vue géométrique en raison du coût élevé autour de cette source.

Une vue dans le plan de la surface de plus faible coût cumulé pour deux sources (S1 et S2) à partir d’un emplacement non source est affichée.

Une vue 3D montrant la même surface de plus faible coût cumulé est présentée ci-dessous. La pente de la surface est plus forte autour de la source la plus coûteuse (le coût s’élève plus rapidement). Cette source a une surface de coût minimum seulement à sa proximité immédiate. Dans les autres cellules de la zone d’étude, la surface appartient à la source située à gauche.

Une vue perspective 3D d’une surface de plus faible coût cumulé pour deux sources est illustrée.

Régions d’allocation sous forme de bassins versants

Comme la surface de coût de friction et la surface de coût cumulé en sortie deviennent plus complexes, vous pouvez continuer d’utiliser les isolignes, la pente et l’exposition pour comprendre le comportement de surfaces de coût cumulé. En outre, les régions d’allocation autour des sources opèrent comme des bassins versants pour la surface de coût cumulé en sortie. Tous les chemins de moindre coût au sein d’une région d’allocation rejoignent la même source. Les bassins versants d’allocation sont associés à des isolignes et une vue 3D dans les exemples ci-dessous.

Les surfaces de coût cumulé les plus complexes, telle que cette surface de temps de déplacement, peut être visualisée précisément en 2D et 3D au moyen d’isolignes (il s’agit d’isochrones dans le cas présent).

Illustration d’une surface de coût cumulé avec des isolignes dans une vue dans le plan 2D.

Une vue 3D de la même surface est illustrée dans l’image suivante. Les falaises à l’arrière-plan forment des interruptions dues à la présence d’une rivière.

Une vue perspective en 3D d’une surface de coût cumulé est affichée.

Les chemins de moindre coût descendent sur la surface de coût cumulé pour parvenir à la source qui définit la zone d’allocation (bassin versant), comme illustré dans l’image suivante :

Une vue perspective en 3D de l’écoulement des chemins de moindre coût vers la surface de coût cumulé est affichée.

L’algorithme de reconstruction de surface est une extension de l’algorithme de réseau

Pour trouver une surface de coût cumulé en ne connaissant que la valeur de la pente la plus forte au niveau de chaque cellule, vous pouvez également utiliser l’algorithme de reconstruction de surface. Cet algorithme est analogue à l’algorithme de chemin le plus court utilisé par les anciens outils de distance de coût. Il inclut une étape supplémentaire pour fournir une approximation du coût cumulé qui ne suit pas l’une des huit directions du réseau. On parle d’étape eikonale. Une brève description en est donnée par la suite ; des informations détaillées sont disponibles dans l’ouvrage de Sethian publié en 1999.

Pour comprendre cette étape en contexte, vous allez rechercher le coût cumulé z5 pour la cellule centrale ci-dessous. Supposons que vous connaissiez tous les coûts cumulés voisins zi. Vous connaissez, par ailleurs, la valeur de pente S de la cellule centrale grâce au raster de coût en entrée.

Figure 4. L’algorithme de reconstruction de surface calcule une hauteur z5 pour la cellule centrale en réalisant plusieurs approximations de cette hauteur à l’aide de la pente du raster de coût de friction en entrée au niveau de la cellule centrale ainsi qu’à partir des hauteurs théoriques connues zi pour les cellules voisines.

Par exemple, une approximation de z5 peut utiliser la diagonale reliant z3 à z5, où z5 = z3 + 1,4 * taille de la cellule * S, comme illustré dans la figure ci-dessus. Dans le cas présent, la valeur S (valeur du raster de coût en entrée) est interprétée comme la pente du triangle abc. Pour de telles approximations de style réseau, seule la pente au niveau de 5 permet de calculer de façon approximative le coût cumulé en z5. Cette méthode est différente de l’algorithme de réseau hérité qui utilise une moyenne des coûts provenant des paires de cellules.

Figure 5. Le calcul par la diagonale est illustré. La pente s de la surface du coût de friction en entrée est interprétée comme la pente de l’hypoténuse du triangle abc.

Huit approximations de réseau peuvent être réalisées dont quatre utilisent des paires de hauteurs existantes comme illustré dans la série des trois figures ci-dessous. Dans notre cas, la valeur du raster de coût en entrée à l’emplacement de la cellule z5 est interprétée comme l’amplitude S de l’inclinaison du plan passant par les deux points connus et l’élévation inconnue z5. À partir de cette relation, vous pouvez calculer z5. Il s’agit de l’étape eikonale.

Figure 6. Les entrées de l’étape eikonale sont illustrées : deux hauteurs, z6 et z8, sont connues.

L’amplitude de l’inclinaison du plan est calculée.

Figure 7. La mesure S du raster de coût est l’amplitude de l’inclinaison du plan qui passe par les deux élévations connues z8 et z6 et l’élévation inconnue z5

La direction de l’inclinaison est calculée.

Figure 8. La direction de l’inclinaison correspond à la valeur d’exposition (direction arrière) pour la cellule z5.

L’étape eikonale récupère également les informations d’exposition en z5, appelée direction arrière.

12 approximations existent maintenant pour l’élévation de la cellule centrale. Le minimum d’entre elles est sélectionné et enregistré comme valeur de coût cumulé z5 pour la cellule centrale. Si vous avez demandé un raster de direction arrière, l’exposition de l’inclinaison (comme décrit au paragraphe précédent) est enregistrée à l’emplacement correspondant dans le raster de direction arrière en sortie.

Ce processus est réitéré pour une cellule chaque fois qu’une nouvelle valeur d’élévation est obtenue pour l’un de ses voisins. À la fin, les valeurs d’élévation cessent de changer et l’algorithme prend fin. Les élévations initiales sont fournies par les sources : elles sont égales à zéro ou à la valeur cumulée initiale par source. Les autres valeurs d’élévation initiales sont définies sur l’infini. Pour obtenir des informations détaillées, reportez-vous à l’ouvrage de Sethian (1999). La mise en œuvre d’Esri est une combinaison des techniques décrites par Sethian (1999) et Zhao (2004).

En conclusion, à partir de la pente de chaque cellule, ces étapes reconstruisent l’élévation de la surface de coût cumulé et la direction de pente la plus forte.

Chemins de moindre coût

Les chemins de moindre coût suivent la direction de pente la plus abrupte sur la surface de coût cumulé. Cette direction, pour une cellule, est illustrée ci-dessus à la figure 8. Le raster de direction arrière en sortie consigne cette direction pour chaque cellule. Vous pouvez utiliser l’outil Chemin optimal comme ligne, avec le raster de direction arrière comme entrée, pour tracer ces chemins à partir de n’importe quelle cellule non source.

Dans les figures ci-dessous, un chemin de moindre coût courbe est illustré ; il part de la cellule non source d de couleur bleue en haut à droite et rejoint la cellule source s qui se trouve en bas. D’un point de vue géométrique, d est plus proche de la source en haut, mais vu le coût élevé autour de la source, il est plus économique d’atteindre s en suivant le chemin en ligne courbe.

La destination d correspond au carré bleu. Le chemin passe par une zone de faible coût jusqu’à la source qu’il atteint de manière plus économique en contournant la source de coût élevée.

Figure 9. La construction des chemins de moindre coût à l’aide de la surface de coût cumulé construite à partir de la surface de coût de friction en entrée de la Figure 3 est illustrée.

Même si le nom ne semble pas intuitif, les emplacements en entrée dans le cadre du chemin de moindre coût sont appelées destinations. Les sources ont été utilisées pour construire la surface et désignent les emplacements où prennent fin les chemins de moindre coût.

Les zones d’allocation autour des sources mettent davantage en évidence que le chemin de moindre coût commençant à la destination rejoint la source du bas et non la source du haut. La zone sélectionnée est ensuite grossie pour montrer la manière dont les valeurs des cellules sont interprétées dans le raster de direction arrière.

L’emplacement de la zone d’étude est signalé par le carré.

Le canevas reliant les centres de cellule de direction arrière entre eux est affiché en gris foncé. Les limites des cellules apparaissent en gris clair et les valeurs des cellules apparaissent sous forme de flèches d’azimut. Lorsque le chemin de moindre coût croise les lignes du canevas, il utilise l’azimut de la cellule de direction arrière la plus proche dans le sens de déplacement pour mettre à jour sa direction. Au sommet du chemin supérieur près de la cellule a, la valeur de direction arrière conservée en a permet de diriger la ligne qui part de ce sommet. La ligne de canevas suivante à croiser est plus proche de la cellule b, aussi son azimut est utilisé pour quitter le deuxième sommet, et ainsi de suite.

Une vue de canevas montrant la façon dont sont interprétées les valeurs des cellules figurant dans le raster de direction arrière est illustrée.

En résumé, les chemins de moindre coût partent et finissent aux centres de cellules. Les sommets des autres chemins peuvent se trouver n’importe où sur le canevas de lignes horizontales et verticales traversant les centres des cellules.

Calcul de la pente effective

Les valeurs de pente décrites dans la section précédente ne proviennent pas au sens strict du raster de coût de friction en entrée. Il existe plusieurs autres entrées qui, ensemble, déterminent la pente effective utilisée par l’algorithme de reconstruction de surface. D’autres rubriques présentent une description détaillée de ces entrées, en particulier l’importance de tenir compte de la direction du mouvement à travers une cellule et du sens de déplacement (depuis une source ou vers celle-ci). La présente rubrique s’intéresse à la manière dont l’algorithme de reconstruction de surface utilise les entrées. Les entrées sont les suivantes :

• L’entrée de coût de friction, C
• L’entrée de surface, S
• Le multiplicateur de coût source, M
• La fonction de facteur horizontal, HF
• La fonction de facteur vertical, VF

La pente effective utilisée par l’algorithme de reconstruction correspond à la formule générale :

Pente effective = C * S * M * HF * VF

Cette valeur est ensuite multipliée par la taille de cellule ou par sqrt(2) * taille de cellule et ajoutée à une hauteur existante pour obtenir l’une des estimations de hauteur de direction de réseau. Une fonction plus complexe de la pente effective est utilisée pour obtenir une estimation de hauteur pour l’étape eikonale.

Pour la pente effective, les unités de coût cumulé doivent être divisées par une distance linéaire (un taux). Si, par exemple, votre surface de coût cumulé consiste à mesurer la durée de déplacement en heures et que la taille de cellule d’analyse est en mètres, la pente effective doit avoir des unités en heures/mètres.

Étant donné que la pente effective est un produit de plusieurs termes, vous devez vous assurer que les unités des termes individuels soient combinées pour produire les unités de pente effective correctes. Si, par exemple, vous utilisez un raster de coût de friction simple pour décrire la durée du déplacement quelle que soit la direction empruntée, les valeurs de cellule du raster de coût de friction doivent avoir des unités en heures/mètres. Par ailleurs, si vous utilisez la fonction de randonnée de Tobler comme fonction de facteur vertical, cette fonction de randonnée aura des unités en heures/mètres et votre surface de coût de friction, le cas échéant, doit être interprétée comme un poids sans unité. Vous devez alors vous assurer que les valeurs de cellule de votre coût de friction peuvent être interprétées de cette manière. Autrement dit, la fonction verticale et le coût de friction ne peuvent pas être tous les deux des taux.

Vous ne contrôlez pas directement la surface en entrée (S). Il s’agit d’un poids sans unité qui étire la taille de cellule afin de couvrir la distance de surface 3D réelle entre les centres de cellule. Dans la Figure 2, l’algorithme de reconstruction de surface calcule une hauteur z5 pour la cellule centrale en réalisant plusieurs approximations de cette hauteur à l’aide de la pente du raster de coût de friction en entrée au niveau de la cellule centrale ainsi qu’à partir des hauteurs théoriques connues pour les cellules voisines.

Les interruptions sont connectées par les sommets

Les interruptions des outils Accumulation de distance et Allocation de distance sont des cellules en entrée qui ne peuvent pas être traversées. Elles sont représentées par des cellules NoData lors du calcul. Elles sont présentées soit explicitement en tant que paramètres de l’outil, soit implicitement en tant que valeurs NoData dans l’une des entrées raster (tel que le raster de coût de friction). Dans le premier cas, elles sont rastérisées et converties en valeurs NoData dans le raster de coût. Étant donné que l’algorithme de reconstruction de surface ne peut pas abaisser l’estimation de hauteur pour une cellule d’interruption, il cherchera un moyen de la contourner.

L’algorithme de reconstruction de surface utilise l’ensemble des huit voisins d’une cellule pour rechercher son estimation de hauteur. Les voisins d’interruption connectés par les angles n’empêchent pas un voisin en diagonale d’être utilisé pour obtenir une estimation de hauteur. Dans l’image ci-dessous, une estimation de hauteur pour z5 peut être obtenue à partir de z3, même si les cellules z2 et z6 sont des interruptions.

S’il est prévu que z2 et z6 fassent partie d’une entité d’interruption linéaire, telle qu’un canal ou une rivière, ce comportement ira à l’encontre de l’intention de l’interruption. Pour éviter ce problème, l’algorithme de reconstruction de surface privilégie la connexion des cellules d’interruption plutôt que la connexion des cellules qui ne forment pas une interruption. Cela signifie que des cellules NoData supplémentaires sont introduites dans le raster de coût pour s’assurer que toutes les cellules d’interruption existantes partagent une arête. Dans l’image ci-dessus, la cellule z5 ou la cellule z3 deviendrait également une cellule d’interruption.

Lorsque vous utilisez des interruptions dans votre analyse, gardez à l’esprit ce comportement et ajuster la taille de cellule en conséquence de manière à préserver la connectivité prévue autour des interruptions. Vous pouvez utiliser l’outil Statistiques focales pour épaissir les versions raster des entités linéaires afin de les utiliser comme interruptions ou réseaux linéaires ne devant pas être interrompus par des cellules d’interruption adjacentes.

Bibliographie

Douglas, D. "Least-cost Path in GIS Using an Accumulated Cost Surface and Slopelines", Cartographica: The International Journal for Geographic Information and Geovisualization, 1994, Vol. 31, No. 3, DOI: 10.3138/D327-0323-2JUT-016M

Goodchild, M.F. "An evaluation of lattice solutions to the problem of corridor location", Environment and Planning A: Economy and Space, 1977, vol. 9, pages 727-738

Sethian, J.A. Level Set Methods and Fast Marching Methods (Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science) 2nd Edition, Cambridge University Press, 2nd edition (June 1, 1999)

Warntz, W. "Transportation, Social Physics, and the Law Of Refraction", The Professional Geographer, 1957, Vol. 9, No. 4, pp. 2-7.

Zhao, H. "A fast sweeping method for Eikonal equations", Mathematics of Computation, 2004, Vol. 74, No. 250, pages 603-627