Outdated version of the documentation. Find the latest one here.

Biblioteca de análisis de redes

A partir de la versión ee19294562 (QGIS >= 1.8) la nueva librería de análisis de redes se agregó a la librería de análisis de nucleo de QGIS. La librería:

  • Crear gráfico matemático de datos geográficos (capas vectoriales de polilínea)

  • implementa métodos básicos de la teoría de grafos (actualmente sólo el algoritmo Dijkstra)

La librería de análisis de redes fue creada por funciones básicas de exportación del complemento núcleo RoadGraph y ahora se puede utilizar los metodos en complementos o directamente de la consola Python.

Información general

Brevemente, un caso de uso típico se puede describir como:

  1. Crear gráfica de geodatos (normalmente de capa vectorial de polilíneas)

  2. ejecutar análisis gráfico

  3. utilizar resultados de análisis (por ejemplo, visualizarlos)

Contruir un gráfico

Lo primero que hay que hacer — es preparar la entrada de datos, que es convertir una capa vectorial en un gráfico. Todas las acciones adicionales utilizarán esta gráfica, no la capa.

Como fuente podemos utilizar una capa vectorial de polilínea. Los nodos de las polilíneas se convierten en vértices del gráfico, y los segmentos de la polilínea son bordes de gráfico. Si varios nodos tienen la misma coordenada entonces ellos tienen el mimso vértice gráfico. Por lo que dos líneas que tienen un nodo en común se conectaran entre si.

Además durante la creación del gráfico se puede “arreglar” (“atar”) a la capa vectorial de entrada cualquier número de puntos adicionales. Para cada punto adicional se encontrará una coincidencia — el vértice gráfico más cercano o el borde gráfico más cercano. En el último caso el borde será dividido y un nuevo vértice se añadirá.

Los atributos de la capa vectorial y la longitud de un borde se puede utilizar como las propiedades de un borde.

Convertir de una capa vectorial a una gráfica se hace utilizando el `Patrón de la programación del constructor<http://en.wikipedia.org/wiki/Builder_pattern>`_. Una gráfica se construye utilizando un llamado director. Hay solo un Director por ahora: QgsLineVectorLayerDirector. El director establece la configuración básica que se utilizará para construir una gráfica de una capa vectorial de línea, utilizado por el constructor para crear la gráfica. Actualmente, con en el caso con el director, solo un constructor existe: QgsGraphBuilder, que crea objetos QgsGraph. Se puede querer implementar su propio constructor que construya un grafo compatible con cada librería como BGL or NetworkX.

Para calcular las propiedades del borde el patrón de programación se utiliza strategy. Por ahora solo QgsDistanceArcProperter estrategicamente esta disponible, que toma en cuenta la longitud de la ruta. Se puede implemenetar su propia estrategia que utilizará todos los parametros necesarios. Por ejemplo, el complemento RoadGraph utiliza una estrategía que calcula el tiempo de viaje mediante la longitud del borde y el valor de la velocidad de los atributos.

Es tiempo de sumergirse en el proceso.

Antes que nada, para utilizar esta librería debemos importar el modulo de análisis de redes

from qgis.networkanalysis import *

Después algunos ejemplos para crear un director

# don't use information about road direction from layer attributes,
# all roads are treated as two-way
director = QgsLineVectorLayerDirector(vLayer, -1, '', '', '', 3)

# use field with index 5 as source of information about road direction.
# one-way roads with direct direction have attribute value "yes",
# one-way roads with reverse direction have the value "1", and accordingly
# bidirectional roads have "no". By default roads are treated as two-way.
# This scheme can be used with OpenStreetMap data
director = QgsLineVectorLayerDirector(vLayer, 5, 'yes', '1', 'no', 3)

Para construir un director debemos pasar a una capa vectorial, que se utilizará como fuente para la estructura gráfica y la información sobre el movimiento permitido en cada segmento de carretera (movimiento unidireccional o bidireccional, dirección directa o inversa). La llamada se parece a esto

director = QgsLineVectorLayerDirector(vl, directionFieldId,
                                      directDirectionValue,
                                      reverseDirectionValue,
                                      bothDirectionValue,
                                      defaultDirection)

Y aquí esta la lista completa de lo que significan estos parámetros:

  • vl — la capa vectorial utilizada para construir la gráfica

  • directionFieldId — índice de la tabla de atributos de campo, donde se almacena información acerca de dirección de carreteras. Si -1, entonces no utilice esta información en absoluto. Un entero.

  • directDirectionValue — el valor del campo de carreteras con dirección directa (mover desde la primer punto de línea a la última). Un texto.

  • reverseDirectionValue — valor del campo de carreteras con dirección inversa (mover del último punto de línea al primero). Un texto.

  • bothDirectionValue — valor de campo para carreteras bidireccionales (para cada carretera podemos mover del primer punto al último y del último al primero). Un texto.

  • defaultDirection — dirección de carretera predeterminada. Este valor se utilizará para esos caminos donde el campo directionFieldId no esta establecido o tiene algun valore diferente de cualquiera de los tres valores especificados anteriormente. Un entero. 1 indica la dirección directa, 2 la dirección inversa, y 3 ambas direcciones.

Es necesario entonces crear una estrategia para calcular propiedades de borde

properter = QgsDistanceArcProperter()

Y decirle al director sobre esta estrategia

director.addProperter(properter)

Ahora podemos utilizar el constructor, que creará el grafo. El constructor de la clase QgsGraphBuilder tomar varios argumentos:

  • src — sistema de referencia de coordenadas a utilizar. Argumento obligatorio.

  • otfEnable — utilizar la reproyección ‘al vuelo’ o no. Por defecto const:True (utilizar OTF).

  • topologyTolerance — tolerancia topologica. Por defecto el valor es 0.

  • ellipsoidID — ellipsoid a utilizar. Por defecto “WGS84”.

# only CRS is set, all other values are defaults
builder = QgsGraphBuilder(myCRS)

También podemos definir varios puntos, que se utilizarán en el análisis. Por ejemplo

startPoint = QgsPoint(82.7112, 55.1672)
endPoint = QgsPoint(83.1879, 54.7079)

Ahora todo está en su lugar para que podamos construir el gráfico y “atar” a estos puntos

tiedPoints = director.makeGraph(builder, [startPoint, endPoint])

Construir el grafo puede tomar tiempo (que depende del número de elementos y tamaño de una capa). tiedPoints es una lista con coordenadas de puntos “tied”. Cuando la operación de construcción se finalizo podemos obtener la gráfica y utilizarlo para el análisis

graph = builder.graph()

Con el siguiente código podemos obtener el índice del vértice de nuestros puntos

startId = graph.findVertex(tiedPoints[0])
endId = graph.findVertex(tiedPoints[1])

Análisis gráfico

El análisis de redes es utilizado para encontrar respuestas a dos preguntas: que vértices estan conectados y cómo encontrar la ruta más corta. Para resolver estos problemas la librería de análisis de redes proporciona el algoritmo Dijkstra.

El algoritmo Dijkstra encuentra la ruta más corta de uno de los vértices del grafo a todos los otros y los valores de los parámetros de optimización, El resultado puede ser representado como un árbol de la ruta más corta.

El árbol del cámino más corto es un grafo ponderado dirigido (o más precisamente – árbol) con las siguientes propiedades:

  • sólo un vértice no tiene bordes entrantes — la raíz del árbol

  • todos los otros vértices sólo tienen un borde entrante

  • Si el vértice B es accesible desde el vértice A, entonces el camino de A a B es la única ruta disponible y es optima (más corta) en este grafo

Para obtener el árbol de la ruta más corta utilice los métodos shortestTree() y dijkstra() de la clase QgsGraphAnalyzer. Es recomendable utilizar el método dijkstra() porque funciona más rápido y utiliza memoria más efectivamente.

El método shortestTree() es útil cuando se desea caminar al rededor del árbol del camino más corto. Siempre crea un nuevo objeto grafo (QgsGraph) y acepta tres variables:

  • fuente — gráfico de entrada

  • startVertexIdx — índice del punto en el árbol (la raíz del árbol)

  • criterionNum — número de propiedad de borde a utilizar (iniciar de 0).

tree = QgsGraphAnalyzer.shortestTree(graph, startId, 0)

El método dijkstra() tiene los mismos argumentos, pero regresa dos arrays. En el primer elemento del array i contiene el índice del borde entrante o -1 si no hay bordes entrantes. En el segundo elemento del array i contiene la distancia de la raíz del árbol al vértice i o DOUBLE_MAX si el vértice i es inalcanzable de la raíz.

(tree, cost) = QgsGraphAnalyzer.dijkstra(graph, startId, 0)

Aquí hay algunos sencillos ejemplos de código para mostrar el árbol de la ruta más corta usando el grafo creado con el método shortestTree() (seleccione la capa de linestring en TOC y reemplace las coordenadas con las propias). Advertencia: utilice este código sólo como ejemplo, cree muchos objetos QgsRubberBand y puede ser lento en grandes conjuntos de datos .

from PyQt4.QtCore import *
from PyQt4.QtGui import *

from qgis.core import *
from qgis.gui import *
from qgis.networkanalysis import *

vl = qgis.utils.iface.mapCanvas().currentLayer()
director = QgsLineVectorLayerDirector(vl, -1, '', '', '', 3)
properter = QgsDistanceArcProperter()
director.addProperter(properter)
crs = qgis.utils.iface.mapCanvas().mapRenderer().destinationCrs()
builder = QgsGraphBuilder(crs)

pStart = QgsPoint(-0.743804, 0.22954)
tiedPoint = director.makeGraph(builder, [pStart])
pStart = tiedPoint[0]

graph = builder.graph()

idStart = graph.findVertex(pStart)

tree = QgsGraphAnalyzer.shortestTree(graph, idStart, 0)

i = 0;
while (i < tree.arcCount()):
  rb = QgsRubberBand(qgis.utils.iface.mapCanvas())
  rb.setColor (Qt.red)
  rb.addPoint (tree.vertex(tree.arc(i).inVertex()).point())
  rb.addPoint (tree.vertex(tree.arc(i).outVertex()).point())
  i = i + 1

La misma cosa pero utilizando el método dijkstra()

from PyQt4.QtCore import *
from PyQt4.QtGui import *

from qgis.core import *
from qgis.gui import *
from qgis.networkanalysis import *

vl = qgis.utils.iface.mapCanvas().currentLayer()
director = QgsLineVectorLayerDirector(vl, -1, '', '', '', 3)
properter = QgsDistanceArcProperter()
director.addProperter(properter)
crs = qgis.utils.iface.mapCanvas().mapRenderer().destinationCrs()
builder = QgsGraphBuilder(crs)

pStart = QgsPoint(-1.37144, 0.543836)
tiedPoint = director.makeGraph(builder, [pStart])
pStart = tiedPoint[0]

graph = builder.graph()

idStart = graph.findVertex(pStart)

(tree, costs) = QgsGraphAnalyzer.dijkstra(graph, idStart, 0)

for edgeId in tree:
  if edgeId == -1:
    continue
  rb = QgsRubberBand(qgis.utils.iface.mapCanvas())
  rb.setColor (Qt.red)
  rb.addPoint (graph.vertex(graph.arc(edgeId).inVertex()).point())
  rb.addPoint (graph.vertex(graph.arc(edgeId).outVertex()).point())

Encontrar la ruta más corta

Para encontrar la ruta optima entre dos puntos, el siguiente enfoque se utiliza. Ambos puntos (inicio A y fin B) son “tied” al grafo cuando es construido. Entonces utiliza los métodos shortestTree() o dijkstra(), nosotros construiremos el árbol de la ruta más corta con raiz en el punto inicial A. En el mismo árbol también encontramos el punto final B y comenzamos a avanzar a través del árbol del punto B al punto A. Todo el algoritmo se puede escribir como

assign Т = B
while Т != A
    add point Т to path
    get incoming edge for point Т
    look for point ТТ, that is start point of this edge
    assign Т = ТТ
add point А to path

En este punto tenemos la ruta, en el formulario de la lista invertida de vértices (los vértices están listados en orden invertida del punto final al punto inicial) que serán visitados durante el viaje por este camino.

Aquí esta el código de ejemplo para la consola Python de QGIS (deberá seleccionar la capa linestring en TOC y en el código reemplazar las coordenadas por las suyas) que usa el método shortestTree()

from PyQt4.QtCore import *
from PyQt4.QtGui import *

from qgis.core import *
from qgis.gui import *
from qgis.networkanalysis import *

vl = qgis.utils.iface.mapCanvas().currentLayer()
director = QgsLineVectorLayerDirector(vl, -1, '', '', '', 3)
properter = QgsDistanceArcProperter()
director.addProperter(properter)
crs = qgis.utils.iface.mapCanvas().mapRenderer().destinationCrs()
builder = QgsGraphBuilder(crs)

pStart = QgsPoint(-0.835953, 0.15679)
pStop = QgsPoint(-1.1027, 0.699986)

tiedPoints = director.makeGraph(builder, [pStart, pStop])
graph = builder.graph()

tStart = tiedPoints[0]
tStop = tiedPoints[1]

idStart = graph.findVertex(tStart)
tree = QgsGraphAnalyzer.shortestTree(graph, idStart, 0)

idStart = tree.findVertex(tStart)
idStop = tree.findVertex(tStop)

if idStop == -1:
  print "Path not found"
else:
  p = []
  while (idStart != idStop):
    l = tree.vertex(idStop).inArc()
    if len(l) == 0:
      break
    e = tree.arc(l[0])
    p.insert(0, tree.vertex(e.inVertex()).point())
    idStop = e.outVertex()

  p.insert(0, tStart)
  rb = QgsRubberBand(qgis.utils.iface.mapCanvas())
  rb.setColor(Qt.red)

  for pnt in p:
    rb.addPoint(pnt)

Y aquí esta el mismo ejemplo pero sin utilizar el método dijkstra()

from PyQt4.QtCore import *
from PyQt4.QtGui import *

from qgis.core import *
from qgis.gui import *
from qgis.networkanalysis import *

vl = qgis.utils.iface.mapCanvas().currentLayer()
director = QgsLineVectorLayerDirector(vl, -1, '', '', '', 3)
properter = QgsDistanceArcProperter()
director.addProperter(properter)
crs = qgis.utils.iface.mapCanvas().mapRenderer().destinationCrs()
builder = QgsGraphBuilder(crs)

pStart = QgsPoint(-0.835953, 0.15679)
pStop = QgsPoint(-1.1027, 0.699986)

tiedPoints = director.makeGraph(builder, [pStart, pStop])
graph = builder.graph()

tStart = tiedPoints[0]
tStop = tiedPoints[1]

idStart = graph.findVertex(tStart)
idStop = graph.findVertex(tStop)

(tree, cost) = QgsGraphAnalyzer.dijkstra(graph, idStart, 0)

if tree[idStop] == -1:
  print "Path not found"
else:
  p = []
  curPos = idStop
  while curPos != idStart:
    p.append(graph.vertex(graph.arc(tree[curPos]).inVertex()).point())
    curPos = graph.arc(tree[curPos]).outVertex();

  p.append(tStart)

  rb = QgsRubberBand(qgis.utils.iface.mapCanvas())
  rb.setColor(Qt.red)

  for pnt in p:
    rb.addPoint(pnt)

Áreas de disponibilidad

El área de la disponibilidad para el vértice A es el subconjunto de vértices del grafo que son accesibles desde el vértice A y el costo de los caminos de la A a estos vértices son no es mayor que cierto valor.

Más claramente esto se puede demostrar con el siguiente ejemplo: “Hay una estación de bomberos ¿Qué partes de la ciudad puede un camión de bomberos alcanzar en 5 minutos? 10 minutos? 15 minutos?”. Las respuestas a estas preguntas son las zonas de la estación de bomberos de la disponibilidad.

Para encontrar las zonas de disponibilidad podemos utilizar el método dijkstra() de la clase QgsGraphAnalyzer. Es suficiente para comparar los elementos del array de costos con un valor predefinido. Si el costo [i] es menor que o igual a un valor predefinido, entonces el vértice i esta dentro de la zona de disponibilidad, de lo contrario esta fuera.

Un problema más difícil es conseguir los límites de la zona de disponibilidad. El borde inferior es el conjunto de vértices que son todavía accesibles, y el borde superior es el conjunto de vértices que no son accesibles. De hecho esto es simple: es la frontera disponibilidad basado en los bordes del árbol de ruta más corta para los que el vértice origen del contorno es más accesible y el vértice destino del borde no lo es.

Aquí tiene un ejemplo

from PyQt4.QtCore import *
from PyQt4.QtGui import *

from qgis.core import *
from qgis.gui import *
from qgis.networkanalysis import *

vl = qgis.utils.iface.mapCanvas().currentLayer()
director = QgsLineVectorLayerDirector(vl, -1, '', '', '', 3)
properter = QgsDistanceArcProperter()
director.addProperter(properter)
crs = qgis.utils.iface.mapCanvas().mapRenderer().destinationCrs()
builder = QgsGraphBuilder(crs)

pStart = QgsPoint(65.5462, 57.1509)
delta = qgis.utils.iface.mapCanvas().getCoordinateTransform().mapUnitsPerPixel() * 1

rb = QgsRubberBand(qgis.utils.iface.mapCanvas(), True)
rb.setColor(Qt.green)
rb.addPoint(QgsPoint(pStart.x() - delta, pStart.y() - delta))
rb.addPoint(QgsPoint(pStart.x() + delta, pStart.y() - delta))
rb.addPoint(QgsPoint(pStart.x() + delta, pStart.y() + delta))
rb.addPoint(QgsPoint(pStart.x() - delta, pStart.y() + delta))

tiedPoints = director.makeGraph(builder, [pStart])
graph = builder.graph()
tStart = tiedPoints[0]

idStart = graph.findVertex(tStart)

(tree, cost) = QgsGraphAnalyzer.dijkstra(graph, idStart, 0)

upperBound = []
r = 2000.0
i = 0
while i < len(cost):
  if cost[i] > r and tree[i] != -1:
    outVertexId = graph.arc(tree [i]).outVertex()
    if cost[outVertexId] < r:
      upperBound.append(i)
  i = i + 1

for i in upperBound:
  centerPoint = graph.vertex(i).point()
  rb = QgsRubberBand(qgis.utils.iface.mapCanvas(), True)
  rb.setColor(Qt.red)
  rb.addPoint(QgsPoint(centerPoint.x() - delta, centerPoint.y() - delta))
  rb.addPoint(QgsPoint(centerPoint.x() + delta, centerPoint.y() - delta))
  rb.addPoint(QgsPoint(centerPoint.x() + delta, centerPoint.y() + delta))
  rb.addPoint(QgsPoint(centerPoint.x() - delta, centerPoint.y() + delta))