withPoints - Familia de funciones

Cuando los puntos también se dan como entrada:

Advertencia

Funciones propuestas para el próximo lanzamineto.

  • No están oficialmente en la versión actual.

  • Es probable que oficialmente formen parte del próximo lanzamiento:

    • Las funciones hacen uso de ANY-INTEGER y ANY-NUMERICAL

    • Es posible que el nombre no cambie. (Pero todavía puede)

    • Es posible que la firma no cambie. (Pero todavía puede)

    • Es posible que la funcionalidad no cambie. (Pero todavía puede)

    • Se han hecho pruebas de pgTap. Pero tal vez necesite más.

    • Es posible que la documentación necesite un refinamiento.

Imágenes

Los vértices al cuadrado son los vértices temporales, los vértices temporales se añaden de acuerdo con el lado de conducción, Las siguientes imágenes muestran visualmente las diferencias sobre cómo dependiendo del lado de conducción se interpretan los datos.

Lado de conducción derecho

_images/rightDrivingSide.png

Lado de conducción izquierdo

_images/leftDrivingSide.png

no importa el lado de conducción

_images/noMatterDrivingSide.png

Introducción

Esta familia de funciones fue pensada para el ruteo de vehículos, pero bien podría funcionar para alguna otra aplicación que no se nos haya ocurrido aún.

La familia de funciones con puntos le da la capacidad de enrutar entre puntos arbitrarios situados fuera del grafo original.

Cuando se le da un punto identificado con un pid al que se está asignando y borde con un identificador edge_id, con una fracción a lo largo de ese borde (desde el origen hasta el destino del borde) y algo de información adicional sobre qué lado del borde se encuentra en el punto, a continuación, el ruteo desde puntos arbitrarios refleja con mayor precisión los vehículos de enrutamiento en las redes de carreteras,

Hablo de una familia de funciones porque incluye diferentes funcionalidades.
  • pgr_withPoints se basa en pgr_dijkstra

  • pgr_withPointsCost se basa en pgr_dijkstraCost

  • pgr_withPointsKSP se basa en pgr_ksp

  • pgr_withPointsDD se basa en pgr_drivingDistance

En todas estas funciones tenemos que ocuparnos de tantos aspectos como sea posible:

  • Debe funcionar para el ruteo:

    • Coches (grafo dirigido)

    • Peatones (grafo no dirigido)

  • Al llegar al punto:

    • A ambos lados de la calle.

    • Llegada obligatoria en el lado de la calle donde se encuentra el punto.

  • Países con:

    • Conducción de lado derecho

    • Conducción de lado izquierdo

  • Algunos puntos son:

    • Permanente, por ejemplo, el conjunto de puntos de los clientes almacenados en una tabla en la base de datos

    • Temporal, por ejemplo, puntos dados a través de una aplicación web

  • La numeración de los puntos se maneja con signo negativo.

    • Los identificadores de punto originales deben ser positivos.

    • La transformación a negativa se realiza internamente.

    • Para obtener resultados para la participación de identificadores de vértices

      • signo positivo es un vértice del grafo original

      • signo negativo es un punto de los puntos temporales

La razón para hacer esto es para evitar confusiones cuando hay un vértice con el mismo número identificador que el identificador de puntos.

Grafo & aristas

  • Permitir \(G_d(V,E)\) donde \(V\) es el conjunto de vértices y \(E\) es el conjunto de aristas sea el gráfico dirigido original.

    • Un borde del edges_sql original es \((id, source, target, cost, reverse\_cost)\) y se generará internamente

      • \((id, source, target, cost)\)

      • \((id, target, source, reverse\_cost)\)

Definición de Punto

  • Un punto se define por el cuadruplicado: \((pid, eid, fraction, side)\)

    • pid es el identificador de punto

    • eid es un identificador de aristas de edges_sql

    • fracción representa dónde se cortará el borde eid.

    • lado Indica el lado de la arista donde se encuentra el punto.

Creación de Vértices Temporales en el grafo

Para la arista (15, 9,12 10, 20), y permite instertar el punto (2, 12, 0.3, r)

En una red de conducción del lado derecho

Desde la primera imagen de arriba:

  • Podemos llegar al punto sólo a través del vértice 9.

  • Sólo afecta a la arista (15, 9,12, 10) por lo que esa arista se elimina.

  • Se mantiene la arista (15, 12, 9, 20).

  • Crear nuevas aristas:

    • (15, 9, -1, 3) arista desde el vértice 9 hasta el punto 1 cuyo costo es de 3

    • (15, -1,12, 7) arista desde el punto 1 hasta el vértice 12 cuyo costo es de 7

En una red de conducción del lado izquierdo

Desde la segunda imagen de arriba:

  • Podemos llegar al punto sólo a través del vértice 12.

  • Sólo afecta a la arista (15, 12,9 20) por lo que esa arista se elimina.

  • Se mantiene la arista (15, 9,12, 10).

  • Crear nuevas aristas:

    • (15, 12,-1, 14) arista del vértice 12 al punto 1 ha costado 14

    • (15, -1, 9, 6) arista el punto 1 hasta el vértice 9 ha costado 6

Recordar

esa fracción es del vértice 9 al vértice 12

Cuando el lado de conducción no importa

De la tercera imagen anterior:

  • Podemos llegar al punto ya sea a través del vértice 12 o a través del vértice 9

  • Se elimina la arista (15, 12, 9, 20).

  • Se elimina la arista (15, 9, 12, 10).

  • Crear nuevas aristas:

    • (15, 12,-1, 14) arista del vértice 12 al punto 1 ha costado 14

    • (15, -1, 9, 6) arista el punto 1 hasta el vértice 9 ha costado 6

    • (15, 9, -1, 3) arista desde el vértice 9 hasta el punto 1 cuyo costo es de 3

    • (15, -1,12, 7) arista desde el punto 1 hasta el vértice 12 cuyo costo es de 7

Ver también

Índices y tablas