Connexion des entités linéaires et détermination de la longueur de la ligne la plus longue

12

J'ai une entité linéaire (voir image) représentant une rivière que j'ai créée à l'aide de l'outil Stream_to_Feature. La table attributaire contient plusieurs enregistrements représentant différentes lignes - le problème est que la ligne la plus longue (facilement reconnaissable visuellement) n'est pas représentée comme une seule ligne dans la table, elle est en fait composée de nombreuses lignes plus petites. Les lignes semblent se toucher, même si elles ne se croisent pas.

Comment puis-je fusionner ces lignes, puis déterminer la longueur de la ligne la plus longue à l'aide d'ArcObjects ou de méthodes manuelles que je peux convertir en ArcObjects? Une solution encore meilleure consisterait à se débarrasser de tous les affluents et à me laisser juste le canal de la rivière en ligne.

Entité linéaire - rivière

Radar
la source
1
Se connectent-ils du tout? Vous avez dit qu'ils ne se croisent pas, mais cela signifie-t-il qu'ils ne partagent pas un sommet?
Nathanus
1
Désolé - j'aurais dû être plus clair. Ils partagent des sommets, mais ne se croisent pas complètement.
Radar
Savez-vous où se trouve l'embouchure de la rivière? La rivière est-elle toujours un arbre (un chemin unique de chaque point d'amont à l'embouchure)?
Kirk Kuykendall
3
En fait, vous ne voulez pas la longueur de la "ligne la plus longue". Cela pourrait être un itinéraire d'un tronçon amont à un autre tronçon amont distant. Cela se produira lorsque deux branches principales du ruisseau se rejoindront près de son embouchure. Au lieu de cela, vous voulez le chemin le plus long entre l'embouchure et tout autre point final sur le flux. (Cette caractérisation n'exige même pas que le ruisseau soit représenté comme un arbre: il peut tresser et avoir des îles.)
whuber
@whuber - votre évaluation est correcte - une idée de la façon dont je peux accomplir cela en utilisant des itinéraires?
Radar

Réponses:

18

Tout d'abord, un petit historique pour expliquer pourquoi ce n'est pas un problème difficile. Le débit à travers une rivière garantit que ses segments, s'ils sont correctement numérisés, peuvent toujours être orientés pour former un graphe acyclique dirigé (DAG). À son tour, un graphique peut être ordonné linéairement si et seulement s'il s'agit d'un DAG, en utilisant une technique connue sous le nom de tri topologique . Le tri topologique est rapide: ses besoins en temps et en espace sont tous les deux O (| E | + | V |) (E = nombre d'arêtes, V = nombre de sommets), ce qui est aussi bon que possible. La création d'un tel ordre linéaire faciliterait la recherche du lit principal du cours d'eau.

Voici donc un schéma d'un algorithme . L'embouchure du ruisseau se trouve le long de son lit principal. Déplacez-vous en amont le long de chaque branche attachée à la bouche (il peut y en avoir plus d'une si la bouche est une confluence) et trouvez récursivement le lit principal menant à cette branche. Sélectionnez la branche pour laquelle la longueur totale est la plus grande: c'est votre "backlink" le long du lit principal.

Pour rendre cela plus clair, je propose un pseudocode (non testé) . L'entrée est un ensemble de segments de ligne (ou arcs) S (comprenant le flux numérisé), chacun ayant deux points d'extrémité distincts début (S) et fin (S) et une longueur positive, longueur (S); et l'embouchure de la rivière p , qui est un point. La sortie est une séquence de segments unissant la bouche au point amont le plus éloigné.

Nous devrons travailler avec des "segments marqués" (S, p). Ceux-ci sont constitués d'un des segments S avec l'un de ses deux points d'extrémité, p . Nous devrons trouver tous les segments S qui partagent un point d'extrémité avec un point de sonde q , marquer ces segments avec leurs autres points d' extrémité et renvoyer l'ensemble:

Procedure Extract(q: point, A: set of segments): Set of marked segments.

Si aucun segment de ce type ne peut être trouvé, Extract doit renvoyer l'ensemble vide. En tant qu'effet secondaire, Extraire doit supprimer tous les segments qu'il renvoie de l'ensemble A, modifiant ainsi A lui-même.

Je ne donne pas une implémentation d'Extract: votre SIG fournira la capacité de sélectionner des segments S partageant un point final avec q . Les marquer consiste simplement à comparer le début (S) et la fin (S) à q et à retourner celui des deux points de terminaison qui ne correspond pas.

Nous sommes maintenant prêts à résoudre le problème.

Procedure LongestUpstreamReach(p: point, A: set of segments): (Array of segments, length)
    A0 = A                        // Optional: preserves A
    C = Extract(p, A0)            // Removes found segments from the set A0!
    L = 0; B = empty array
    For each (S,q) in C:          // Loop over the segments meeting point p
        (B0, M) = LongestUpstreamReach(q, A0)
        If (length(S) + M > L) then
            B = append(S, B0)
            L = length(S) + M
        End if
    End for
    Return (B, L)
End LongestUpstreamReach

La procédure "append (S, B0)" colle le segment S à la fin du tableau B0 et renvoie le nouveau tableau.

(Si le flux est vraiment un arbre: pas d'îles, de lacs, de tresses, etc. - alors vous pouvez vous passer de l'étape de copier A dans A0 .)

La question d'origine est répondue en formant l'union des segments retournés par LongestUpstreamReach.

Pour illustrer cela , considérons le flux dans la carte d'origine. Supposons qu'il soit numérisé comme une collection de sept arcs. L'arc a va de l'embouchure au point 0 (haut de la carte, à droite sur la figure ci-dessous, qui est tournée) en amont jusqu'à la première confluence au point 1. C'est un arc long, disons 8 unités de long. L'arc b se ramifie à gauche (sur la carte) et est court, d'environ 2 unités de long. L'arc c se ramifie vers la droite et mesure environ 4 unités de long, etc. Les lettres "b", "d" et "f" désignent les branches de gauche lorsque nous allons de haut en bas sur la carte, et "a", "c", "e" et "g" les autres branches, et en numérotant les sommets de 0 à 7, nous pouvons représenter abstraitement le graphique comme la collection d'arcs

A = {a=(0,1), b=(1,2), c=(1,3), d=(3,4), e=(3,5), f=(5,6), g=(5,7)}

Je suppose qu'ils ont respectivement des longueurs 8, 2, 4, 1, 2, 2, 2 pour un à g . La bouche est au sommet 0.

Figure

Le premier exemple est l'appel à Extraire (5, {f, g}). Il renvoie l'ensemble des segments marqués {(f, 6), (g, 7)}. Notez que le sommet 5 est à la confluence des arcs f et g (les deux arcs au bas de la carte) et que (f, 6) et (g, 7) marquent chacun de ces arcs avec leurs extrémités en amont .

L'exemple suivant est l'appel à LongestUpstreamReach (0, A). La première action qu'il prend est l'appel à Extraire (0, A). Cela renvoie un ensemble contenant le segment marqué (a, 1) et il supprime le segment a de l'ensemble A0 , qui est maintenant égal à {b, c, d, e, f, g}. Il y a une itération de la boucle, où (S, q) = (a, 1). Pendant cette itération, un appel est effectué vers LongestUpstreamReach (1, A0). Récursivement, il doit renvoyer la séquence (g, e, c) ou (f, e, c): les deux sont également valables. La longueur (M) qu'elle renvoie est 4 + 2 + 2 = 8. (Notez que LongestUpstreamReach ne modifie pas A0 .) À la fin de la boucle, segmentez aa été ajoutée au lit du cours d'eau et la longueur a été augmentée à 8 + 8 = 16. Ainsi, la première valeur de retour consiste soit en la séquence (g, e, c, a) ou (f, e, c, a), avec une longueur de 16 dans les deux cas pour la deuxième valeur de retour. Cela montre comment LongestUpstreamReach se déplace juste en amont de l'embouchure, en sélectionnant à chaque confluence la branche avec la plus longue distance à parcourir, et garde une trace des segments traversés le long de son itinéraire.

Une implémentation plus efficace est possible lorsqu'il y a beaucoup de tresses et d'îlots, mais dans la plupart des cas, il y aura peu d'efforts inutiles si LongestUpstreamReach est implémenté exactement comme indiqué, car à chaque confluent il n'y a pas de chevauchement entre les recherches dans les différentes branches: l'informatique le temps (et la profondeur de pile) sera directement proportionnel au nombre total de segments.

whuber
la source
+1 Maintenant, si seulement ils l'avaient su avant de nommer la rivière Missouri.
Kirk Kuykendall
1
@Kirk L'exploration récursive de l'Ouest américain au début des années 1800 n'a pas été facile :-).
whuber
c'est incroyablement utile! Je vais voir si je peux obtenir cette configuration dans mon SIG et partager du code utile une fois que je le ferai fonctionner. À votre santé!
Radar
Nice answer whuber
Ragi Yaser Burhum
2

L' outil Ligne non fractionnée peut être utile pour ce que vous essayez de faire, bien que vous deviez deviner une méthode pour différencier une branche de flux d'une autre (pour le champ de dissolution). Cela suppose toutefois que vous disposez d'une licence ArcInfo.

Si vous ne disposez pas d'une telle licence, vous pouvez envisager l'approche ArcObjects en prenant le XY de chaque sommet, en remplissant un IPointCollectionavec eux, puis en créant un en IGeometrytant que PolyLineClass.

Nathanus
la source
1

Vous pouvez utiliser RivEX, c'est un outil ArcGIS 9.1 (qui fonctionnera en 9.3 et 10). Il dispose d'outils pour identifier les problèmes topologiques des réseaux fluviaux et de nombreux outils de traitement. Un tel outil trouve la tige principale .

Hornbydd
la source