Comment simplifier un réseau routable?

24

J'ai un graphe de réseau que je dois simplifier dans le sens de réduire le nombre d'arêtes . L'idée serait de fusionner les nœuds proches les uns des autres et de supprimer les bords courts de connexion.

Comment cela pourrait-il être réalisé dans PostGIS ou GRASS? Ou existe-t-il de meilleures approches pour simplifier automatiquement un réseau comme celui-ci?

J'ai déjà essayé la fonction ST_SnapToGrid mais je ne suis pas satisfait des résultats (gris = original, noir = cassé):

entrez la description de l'image ici

obscur
la source
1
Faites-vous cela pour simplifier une analyse basée sur le réseau ou à des fins d'affichage? Si c'est le premier, quelle analyse sera effectuée?
whuber
C'est pour l'analyse du chemin le plus court.
underdark
2
Parce que la plupart des algorithmes de chemin le plus court sont O (E + V), peut-être n'avez-vous même pas besoin de cette simplification? À l'autre extrême, pour de telles analyses, vous pouvez souvent apporter des simplifications radicalement plus agressives. Par exemple, cet ensemble de trois segments parallèles et leurs segments adjacents à gauche (ressemblant à un H-in-a-box) peuvent être remplacés par un triangle si aucune origine ou destination ne se trouve dans ces segments. Je mentionne cela parce que je suis sûr qu'il existe du code (non SIG) pour de telles opérations sur des graphiques (abstraits).
whuber
Voulez-vous conserver la géométrie des arêtes (par exemple des courbes) ou est-ce que le maintien de la topologie + nœud XY est suffisant? De plus, devez-vous vous assurer que les nœuds à différents Z (par exemple survols) ne s'emboîtent pas?
AnserGIS
La topologie est la clé. La géométrie peut changer un peu. L'ordre Z doit rester intact.
underdark

Réponses:

7

Le plus proche que je suis venu jusqu'ici est le suivant:

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

Il claque les routes avec une tolérance de 5 mètres et supprime toutes les lignes de longueur nulle. Ce n'est pas une solution optimale car elle semble s'aligner de manière plutôt aléatoire sur un sommet.

entrez la description de l'image ici

obscur
la source
En effet, le résultat n'est peut-être pas précis mais cette utilisation de v.clean est intéressante, merci pour le partage
simo
Cette image est-elle créée dans l'herbe?
NetConstructor.com
L'image montre les résultats de GRASS v.clean visualisés dans QGIS.
underdark
Y a-t-il des problèmes avec le maintien des «intersections étranges» ou des routes séparées par le niveau?
dassouki
Que diriez-vous de traiter ST_SnapToGrid après v.clean?
kttii
5

Avez-vous essayé le GRASS v.generalize ?

v.generalizevous permet de choisir l'algorithme de généralisation avec l' attribut method . Il y en a un tas: douglas, douglas_reduction, lang, reduction, reumann, boyle, slide_averaging, distance_weighting, chaiken, hermite, serpents, réseau, déplacement .

Et paramètres supplémentaires threshold, degree_thresh, angle_thresh(selon l'algorithme choisi) peut vous aider à obtenir un résultat précis.

Voici un tutoriel .

simo
la source
Merci pour le lien. J'essaie, mais je ne sais pas vraiment quelle combinaison de valeurs de méthode et de seuils donnera le résultat que je recherche.
underdark
Je ne peux vraiment pas trouver de méthode v.generalize qui fera ce que je veux.
underdark
2
C'est dommage, la commande est riche de nombreux algorithmes mais comme vous l'avez dit précédemment, elle est probablement assez complexe à configurer pour obtenir le résultat attendu. Peut-être un gourou des algorithmes de généralisation, ici? Avez-vous également essayé la méthode des serpents ?
simo
Pas un algo-gourou ici, mais je trouve que la méthode des serpents est la meilleure pour certaines de mes courses v.genralize que j'ai faites dans le passé.
maning
1
Pour mémoire, les paramètres ont été simplifiés à ce jour dans GRASS SVN. Faire partie de GRASS 6.4.2.
markusN
4

Je ne l'ai pas fait mais je pense que je peux suggérer une direction.

  1. Créez une topologie avec PostGIS pour votre graphique.
  2. Trouvez tous les nœuds avec seulement deux arêtes.
  3. Soignez les bords.

ST_ModEdgeHeal fusionnera un bord dans l'autre. ST_NewEdgeHeal remplacera les deux par un nouveau bord.

Manuel de topologie PostGIS

Sean
la source
Merci @Sean. Est-ce que cela fera autre chose que de fusionner deux bords? Une idée sur la façon de supprimer les bords courts et de rapprocher leurs nœuds?
underdark
@Underdark, je ne vois rien de simple. Vous pouvez tout faire en PL / SQL mais cela n'aide probablement pas. Pouvez-vous exécuter ST_SnapToGrid en premier?
Sean
1

@underdark, je vois que vous avez écrit un outil pour densifier les lignes dans Sextante. Par conséquent, je suggère l'algorithme suivant pour éviter de prendre "au hasard" un de vos points.

Sélectionnez les segments de ligne dont vous souhaitez vous débarrasser en fonction de leur longueur.

Pour chacun de ces segments, créez un point au point médian

Supprimer le petit segment

Vous pouvez maintenant utiliser ST_Snap dans PostGIS (voir l'exemple ici )

EDIT: notez que dans votre cas, vous pouvez également utiliser v.net en premier afin de supprimer les pseudo-nœuds (nœud qui ne connecte que deux lignes)

radouxju
la source
Veuillez expliquer comment v.net peut être utilisé pour supprimer les pseudo-nœuds. Merci
osmjit
0

Voici comment Michaël Michaud a analysé cela sur la liste des développeurs 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
la source
Merci d'avoir posté cette réponse. Je suis un peu confus pourquoi vous forceriez le graphique à être plan. Après tout, les réseaux de rues ne sont pas des graphiques plans (ponts, tunnels).
underdark
Seulement parce que Michaël a fait un test rapide avec les outils graphiques existants qu'il a écrits pour OpenJUMP et qu'ils ne prennent pas en charge les graphiques non planaires pour le moment. Ignorez la première étape si QGIS et GRASS ont des outils similaires qui prennent en charge les graphiques non plans.
user30184
Je pense que c'est la bonne approche - séparer le réseau en graphiques planaires. Dans chaque graphique planaire, le problème est plus simple - par exemple, on pourrait utiliser l'approche ci-dessus, ou simplement trianguler et désherber le TIN des bords de route courts. Ensuite, extrayez à nouveau les bords de la route et fusionnez les calques.
AnserGIS