Ruta más corta utilizando puntos OSM interpolados

Question

Tengo un conjunto de puntos GPS que he conectado a la red OSM. En la siguiente captura de pantalla los puntos GPS son rojos, los puntos fijados son verdes.

Quiero calcular el camino más corto que incluya todos estos puntos verdes. Mi solución es calcular el camino más corto entre cada par de puntos y finalmente concatenar los resultados.

Mi problema es que dijkstra_sp no acepta puntos arbitrarios en la red OSM. Mis puntos ajustados no están necesariamente en la tabla de caminos porque fueron calculados usando la siguiente lógica.

1. Encuentra el camino más cercano a un punto GPS dado.
2. Utilizando la interpolación, encuentra el punto más cercano en este camino al punto GPS.

Los puntos encajados no figuran en la tabla de vías porque se obtuvieron por interpolación.

Así que mi pregunta es: ¿Cómo puedo calcular el camino más corto entre dos puntos de la red OSM que no están necesariamente en la tabla de caminos?

Answer 1

Resolvimos el mismo problema con aristas y vértices temporales. Ajustamos nuestras coordenadas GPS a una arista e de v1 a v2 y obtuvimos un desplazamiento entre 0 y 1:

segOffset := line_locate_point(geom(e), Point(coords);

Con esto creamos un nuevo Punto() y fuera de este un nuevo vértice v_tmp:

line_interpolate_point(geom(e), segOffset);

A continuación, dividimos nuestra arista e1 en dos nuevas aristas e_tmp1 de v1 a v_tmp y e_tmp2 de v_tmp a v2. (Podría ser necesario dividirla en 4 aristas temporales...)

Con nuestro objetivo hicimos lo mismo. Entonces empezamos el pgrouting con nuestros nuevos vértices v_tmp_source, v_tmp_dest y listo.

Answer 2

Hice coincidir los nodos más cercanos y utilicé pgrouting para encontrar la ruta entre estos nodos. Buscaba la distancia total, así que sumé las dos distancias punto-nodo.

Tenía un límite máximo de lo cerca que tenía que estar un nodo para ser aceptable.

La matemática sería más complicada/lenta, pero se podría hacer lo mismo con las aristas si se utilizara un algoritmo de pgrouting que trabajara en términos de aristas en lugar de nodos.

Answer 3

Tu problema me recuerda a un caso similar que tuvimos que resolver hace unos años: alguien dibuja un camino (linetring) sobre un mapa raster y teníamos que hacer coincidir este camino con la red de carreteras subyacente.

Esto parece ser similar a sus puntos GPS rojos. Al igual que tú, hemos supuesto que podemos buscar el camino más corto entre estos puntos.

Como de esto hace tanto tiempo, ya no recuerdo los detalles. Pero publicamos la(s) función(es) en "matching.sql", que ya forma parte de pgRouting. Sin embargo, no hay documentación. Lo siento. Pero tal vez la lectura de la fuente de SQL le da una idea de cómo funciona: https://github.com/pgRouting/pgrouting/blob/master/core/sql/matching.sql