Comment simplifier un réseau routable?

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é):

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.

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 .

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

@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)

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