Como simplificar uma rede roteável?

24

Eu tenho um gráfico de rede que preciso simplificar no sentido de reduzir o número de arestas . A idéia seria mesclar nós localizados próximos e remover as arestas curtas de conexão.

Como isso pode ser alcançado no PostGIS ou GRASS? Ou existem abordagens melhores para simplificar automaticamente uma rede como essa?

Eu já tentei a função ST_SnapToGrid, mas não estou satisfeito com os resultados (cinza = original, preto = encaixado):

insira a descrição da imagem aqui

underdark
fonte
11
Você está fazendo isso para simplificar uma análise baseada em rede ou para fins de exibição? Se for o primeiro, que análise será realizada?
whuber
É para análise de caminho mais curto.
Underdark
2
Como muitos dos algoritmos de caminho mais curto são O (E + V), talvez você nem precise dessa simplificação? No outro extremo, para tais análises, muitas vezes você pode fazer simplificações drasticamente mais agressivas. Por exemplo, esse conjunto de três segmentos paralelos e seus segmentos adjacentes à esquerda (parecendo um H-in-a-box) pode ser substituído por um triângulo se nenhuma origem ou destino estiver dentro desses segmentos. Menciono isso porque tenho certeza de que existe um código (não GIS) para essas operações em gráficos (abstratos).
whuber
Deseja manter a geometria das arestas (por exemplo, curvas) ou apenas manter a topologia + nó XY suficiente? Além disso, você precisa garantir que os nós em Z diferentes (por exemplo, sobrevôos) não se encaixem?
AnserGIS
Topologia é a chave. A geometria pode mudar um pouco. A ordem Z deve permanecer intacta.
Subterrâneo

Respostas:

7

O mais próximo que cheguei até agora é este:

v.clean input=roads output=snap5rmline tool=snap,rmline thresh=5 

Está quebrando as estradas com uma tolerância de 5 metros e removendo todas as linhas de comprimento zero. Não é uma solução ideal, pois parece se encaixar aleatoriamente em algum vértice.

insira a descrição da imagem aqui

underdark
fonte
Na verdade, o resultado talvez não seja preciso, mas que o uso de v.clean é interessante, obrigado por compartilhar
simo
Essa imagem é criada na grama?
NetConstructor.com 5/11/11
A imagem mostra os resultados do GRASS v.clean visualizado no QGIS.
underdark
Algum problema com a manutenção de "interseções estranhas" ou estradas separadas?
Dassouki 29/05
Que tal processar ST_SnapToGrid após v.clean?
kttii
5

Você já experimentou o GRASS v.generalize ?

v.generalizepermite escolher o algoritmo de generalização com o atributo method Há um monte: douglas, douglas_reduction, lang, redução, reumann, boyle, deslizamento de média, distance_weighting, chaiken, hermite, cobras, rede, deslocamento .

E parâmetros adicionais, como threshold, degree_thresh, angle_thresh(dependendo do algoritmo escolhido) pode ajudá-lo a obter um resultado preciso.

Aí vem um tutorial .

simo
fonte
Obrigado pelo link. Estou tentando, mas realmente não entendo qual combinação de método e valores de limites dará o resultado que estou procurando.
Underdark
Realmente não consigo encontrar um método v.generalize que faça o que eu quero.
Underdark
2
É uma pena, o comando é rico em muitos algoritmos, mas como você disse antes, provavelmente é bastante complexo de configurar para obter o resultado esperado. Talvez um guru de algoritmos de generalização, aqui? Você já tentou o método das cobras ?
simo
Não é um algo-guru aqui, mas acho o método snakes o melhor para algumas das minhas execuções v.genralize que fiz no passado.
maning
11
Para o registro, os parâmetros foram simplificados até hoje no GRASS SVN. Para se tornar parte do GRASS 6.4.2.
markusN
4

Eu não fiz isso, mas acho que posso sugerir uma direção.

  1. Crie uma topologia com o PostGIS para o seu gráfico.
  2. Encontre todos os nós com apenas duas arestas.
  3. Cure as bordas.

ST_ModEdgeHeal mesclará uma borda na outra. ST_NewEdgeHeal substituirá ambos por uma nova aresta.

Manual de topologia do PostGIS

Sean
fonte
Obrigado @Sean. Isso fará outra coisa senão mesclar duas arestas? Alguma idéia de como remover arestas curtas e encaixar seus nós?
Underdark
@ Underdark, não vejo nada simples. Você pode fazer tudo em PL / SQL, mas isso provavelmente não ajuda. Você pode executar o ST_SnapToGrid primeiro?
22711 Sean
1

@underdark, vejo que você escreveu uma ferramenta para densificar linhas no Sextante. Por isso, sugiro o seguinte algoritmo para evitar o encaixe "aleatório" de um dos seus pontos.

Selecione os segmentos de linha dos quais deseja se livrar com base no comprimento.

Para cada um desses segmentos, crie um ponto no ponto do meio

Exclua o pequeno segmento

Agora você pode usar o ST_Snap no PostGIS (veja o exemplo aqui )

EDIT: observe que, no seu caso, você também pode usar o v.net primeiro para remover os pseudo-nós (nó que conecta apenas duas linhas)

radouxju
fonte
Por favor, elabore como o v.net pode ser usado para remover pseudo-nós. Obrigado
osmjit
0

Encaminhando como Michaël Michaud analisou isso na lista de desenvolvedores do OpenJUMP:

> Interesting question. There has been so much research works about
> generalization that it is surely not a simple task. I have tested the
> following approach with mitigated results :
> - make the layer planar with the noder plugin
> - detect small cycles with the graph plugin
> - merge adjacent cycles
> - create a point inside each cycles surface
> - remove network segments along these cycles (query + DE-9IM)
> - detect roads touching the cycles
> - project the center points of cycles to the road endpoints ==> replace small roundabout by simple nodes
> 
> Possible improvements (probably need a dedicated plugin)
> - make it work on non planar graph (or just remove bridges/tunnels from the graph)
> - replace small edges between two nodes with degree 3+ by a single node,    not only small cycles
> - process iteratively starting with smallest edges/cycles
user30184
fonte
Obrigado por postar esta resposta. Estou um pouco confuso por que você forçaria o gráfico a planar. Afinal, as redes de ruas não são gráficos planares (pontes, túneis).
Underdark
Somente porque Michaël fez um teste rápido com as ferramentas gráficas existentes que ele escreveu para o OpenJUMP e elas não suportam gráficos não planares no momento. Pule o primeiro passo se o QGIS e o GRASS tiverem ferramentas semelhantes que suportam gráficos não planares.
User30184
Eu acho que essa é a abordagem correta - separe a rede em gráficos planares. Em cada gráfico planar, o problema é mais simples - por exemplo, pode-se usar a abordagem acima, ou simplesmente triangular e eliminar o NTI das margens curtas da estrada. Em seguida, extraia as arestas da estrada novamente e junte as camadas.
AnserGIS