¿Cómo simplificar una red enrutable?

Question

Tengo un grafo de red que necesito simplificar en el sentido de reducir el número de aristas . La idea sería fusionar los nodos que se encuentran cerca y eliminar las aristas cortas de conexión.

¿Cómo podría lograrse esto en PostGIS o GRASS? ¿O existen mejores métodos para simplificar automáticamente una red de este tipo?

Ya he probado la función ST_SnapToGrid pero no estoy contento con los resultados (gris = original, negro = snapped):

Answer 1

Lo más cerca que he llegado hasta ahora es esto:

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

Está ajustando las carreteras con una tolerancia de 5 metros y eliminando todas las líneas de longitud cero. No es una solución óptima, ya que parece que se ajusta aleatoriamente a algún vértice.

Answer 2

¿Has probado el GRASS v.generalizar ?

v.generalize le permite elegir el algoritmo de generalización con el método atributo. Hay un montón : douglas,reducción_douglas,lang,reducción,reumann,boyle,promedio_deslizante,ponderación_distancia,chaiken,hermite,serpientes,red,desplazamiento .

Y parámetros adicionales como threshold , degree_thresh , angle_thresh (dependiendo del algoritmo elegido) puede ayudarle a obtener un resultado preciso.

Aquí viene un tutorial .

Answer 3

No lo he hecho pero creo que puedo sugerir una dirección.

1. Cree una topología con PostGIS para su gráfico.
2. Encuentra todos los nodos con sólo dos aristas.
3. Cura los bordes.

ST_ModEdgeHeal fusionará un borde con el otro. ST_NewEdgeHeal sustituirá ambas por una nueva arista.

Manual de topología PostGIS

Answer 4

@underdark , veo que has escrito un herramienta para densificar líneas en Sextante. Por lo tanto, sugiero el siguiente algoritmo para evitar "al azar" romper uno de sus puntos.

Seleccione los segmentos de línea que desea eliminar en función de su longitud.

Para cada uno de esos segmentos, crea un punto en el punto medio

Eliminar el segmento pequeño

Ahora puede utilizar ST_Snap en PostGIS (véase el ejemplo aquí )

EDIT: tenga en cuenta que en su caso, también podría utilizar v.net primero para eliminar los pseudonodos (nodos que conectan sólo dos líneas)

Answer 5

Reenvío de cómo Michaël Michaud analizó esto en la lista de desarrolladores de 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