Conectando recursos de linha e determinando o comprimento da linha mais longa

12

Eu tenho um recurso de linha (veja a imagem) representando um rio que eu criei usando a ferramenta Stream_to_Feature. A tabela de atributos contém vários registros que representam linhas diferentes - o problema é a linha mais longa (visualmente facilmente distinguível) não é representada como uma única linha na tabela; na verdade, é composta de muitas linhas menores. As linhas parecem estar tocando, embora não se cruzem.

Como mesclar essas linhas e determinar o comprimento da linha mais longa usando o ArcObjects ou métodos manuais que posso converter em ArcObjects? Uma solução ainda melhor envolveria me livrar de todos os afluentes e me deixar com apenas o canal do rio como uma linha.

Recurso de linha - rio

Radar
fonte
1
Eles se conectam? Você disse que eles não cruzam, mas isso significa que eles não compartilham um vértice?
Nathanus
1
Desculpe - eu deveria ter sido mais claro. Eles compartilham vértices, mas não se cruzam completamente.
Radar
Você sabe onde fica a foz do rio? O rio é sempre uma árvore (um caminho único de cada ponto de cabeceira até a foz)?
Kirk Kuykendall
3
Na verdade, você não quer o comprimento da "linha mais longa". Essa poderia ser uma rota de um alcance a montante para outro alcance a montante remoto. Isso acontecerá quando dois ramos principais do córrego se juntarem perto de sua boca. Em vez disso, você deseja a rota mais longa entre a boca e qualquer outro ponto de extremidade no fluxo. (Esta caracterização nem sequer exigem o fluxo de ser representado como uma árvore:. Pode trança e tem ilhas)
whuber
@whuber - sua avaliação está correta - alguma idéia de como fazer isso usando rotas?
Radar

Respostas:

18

Primeiro, um pequeno histórico para indicar por que esse não é um problema difícil. O fluxo através de um rio garante que seus segmentos, se digitalizados corretamente, sempre possam ser orientados para formar um gráfico acíclico direcionado (DAG). Por sua vez, um gráfico pode ser ordenado linearmente se e somente se for um DAG, usando uma técnica conhecida como classificação topológica . A classificação topológica é rápida: seus requisitos de tempo e espaço são O (| E | + | V |) (E = número de arestas, V = número de vértices), o que é o melhor possível. Criar uma ordem linear desse tipo facilitaria a localização do leito principal do fluxo.

Aqui, então, está um esboço de um algoritmo . A boca do riacho fica ao longo de seu leito principal. Mova-se rio acima ao longo de cada ramo anexado à boca (pode haver mais de um, se a boca for uma confluência) e encontre recursivamente o leito principal que leva até esse ramo. Selecione o ramo para o qual o comprimento total é maior: esse é o seu "backlink" ao longo da cama principal.

Para deixar isso mais claro, ofereço alguns pseudocódigos (não testados) . A entrada é um conjunto de segmentos de linha (ou arcos) S (compreendendo o fluxo digitalizado), cada um tendo dois pontos finais distintos início (S) e final (S) e um comprimento positivo, comprimento (S); e a foz do rio p , que é um ponto. A saída é uma sequência de segmentos que unem a boca ao ponto a montante mais distante.

Precisamos trabalhar com "segmentos marcados" (S, p). Estes consistem em um dos segmentos S, juntamente com um de seus dois pontos finais, p . Precisamos encontrar todos os segmentos S que compartilham um ponto de extremidade com um ponto de sonda q , marcar esses segmentos com seus outros pontos de extremidade e retornar o conjunto:

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

Quando nenhum segmento é encontrado, o Extract deve retornar o conjunto vazio. Como efeito colateral, o Extract deve remover todos os segmentos que está retornando do conjunto A, modificando assim o próprio A.

Não estou fornecendo uma implementação do Extract: seu GIS fornecerá a capacidade de selecionar os segmentos S que compartilham um terminal com q . Marcá-los é simplesmente uma questão de comparar o início (S) e o final (S) com q e retornar o que for um dos dois pontos de extremidade que não corresponde.

Agora estamos prontos para resolver o problema.

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

O procedimento "acrescentar (S, B0)" adere ao segmento S no final da matriz B0 e retorna a nova matriz.

(Se o fluxo é realmente uma árvore: sem ilhas, lagos, tranças, etc. - você pode dispensar a etapa de copiar A para A0 .)

A pergunta original é respondida através da formação da união dos segmentos retornados pelo LongestUpstreamReach.

Para ilustrar , vamos considerar o fluxo no mapa original. Suponha que seja digitalizado como uma coleção de sete arcos. O arco a vai da boca no ponto 0 (parte superior do mapa, à direita na figura abaixo, que é girada) a montante da primeira confluência no ponto 1. É um arco longo, digamos 8 unidades de comprimento. O arco b se ramifica para a esquerda (no mapa) e é curto, com cerca de 2 unidades de comprimento. O arco c se ramifica para a direita e tem cerca de 4 unidades de comprimento etc. Deixar "b", "d" e "f" denotarem os ramos do lado esquerdo à medida que avançamos de cima para baixo no mapa e "a", "c", "e" e "g" os outros ramos e, numerando os vértices de 0 a 7, podemos abstratamente representar o gráfico como a coleção de arcos

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

Suponho que eles tenham comprimentos 8, 2, 4, 1, 2, 2, 2 para a a g , respectivamente. A boca é o vértice 0.

Figura

O primeiro exemplo é a chamada para Extrair (5, {f, g}). Retorna o conjunto de segmentos marcados {(f, 6), (g, 7)}. Note-se que 5 vértice está na confluência dos arcos de f e g (os dois arcos na parte inferior do mapa) e que (f, 6) e (g, 7) marcar cada um desses arcos com as suas montante de extremidade.

O próximo exemplo é a chamada para LongestUpstreamReach (0, A). A primeira ação a ser executada é a chamada para Extrair (0, A). Isso retorna um conjunto contendo o segmento marcado (a, 1) e remove o segmento a do conjunto A0 , que agora é igual a {b, c, d, e, f, g}. Há uma iteração do loop, onde (S, q) = (a, 1). Durante essa iteração, é feita uma chamada para LongestUpstreamReach (1, A0). Recursivamente, ele deve retornar a sequência (g, e, c) ou (f, e, c): ambas são igualmente válidas. O comprimento (M) que ele retorna é 4 + 2 + 2 = 8. (Observe que LongestUpstreamReach não modifica A0 .) No final do loop, segmente umfoi anexado ao leito do fluxo e o comprimento foi aumentado para 8 + 8 = 16. Portanto, o primeiro valor de retorno consiste na sequência (g, e, c, a) ou (f, e, c, a), com um comprimento de 16 em ambos os casos, para o segundo valor de retorno. Isso mostra como o LongestUpstreamReach apenas se move a montante da boca, selecionando em cada confluência o ramo com a maior distância ainda a percorrer e acompanha os segmentos percorridos ao longo de sua rota.

Uma implementação mais eficiente é possível quando há muitas tranças e ilhas, mas, para a maioria dos propósitos, haverá pouco esforço desperdiçado se o LongestUpstreamReach for implementado exatamente como mostrado, porque em cada confluência não há sobreposição entre as pesquisas nos vários ramos: a computação o tempo (e a profundidade da pilha) serão diretamente proporcionais ao número total de segmentos.

whuber
fonte
+1 Agora, se eles soubessem disso antes de nomear o rio Missouri.
21411 Kirk Kuykendall
1
@Kirk A exploração recursiva do oeste americano no início de 1800 não foi fácil :-).
whuber
isso é incrivelmente útil! Vou ver se consigo obter essa configuração dentro do meu GIS e compartilhar algum código útil assim que o fizer funcionar. Felicidades!
Radar
Agradável resposta whuber
Ragi Yaser Burhum
2

A ferramenta Linha não dividida pode ser útil para o que você está tentando fazer, embora seja necessário adivinhar algum método para diferenciar uma ramificação de fluxo de outra (para o campo de dissolução). Isso pressupõe que você tenha uma licença do ArcInfo.

Se você não possui uma licença, considere a abordagem do ArcObjects usando o XY de cada vértice, preenchendo um IPointCollectioncom eles e criando um IGeometrycomo a PolyLineClass.

Nathanus
fonte
1

Você pode usar o RivEX , é uma ferramenta do ArcGIS 9.1 (que funcionará nas 9.3 e 10). Possui ferramentas para identificar problemas topológicos com redes fluviais e muitas ferramentas de processamento. Uma dessas ferramentas encontra o tronco principal .

Hornbydd
fonte