Ruta más corta utilizando puntos OSM interpolados

8

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 ajustados son verdes. ingrese la descripción de la imagen aquí

Quiero calcular la ruta más corta que incluye todos estos puntos verdes. Mi solución es calcular la ruta más corta entre cada par de puntos y finalmente concatenar los resultados.

Mi problema es que dijkstra_sp no aceptará puntos arbitrarios en la red OSM. Mis puntos ajustados no están necesariamente en la tabla de formas porque se calcularon utilizando la siguiente lógica.

  1. Encuentra la forma más cercana a un punto GPS dado.
  2. Usando la interpolación, encuentre el punto más cercano de esta manera al punto GPS.

Los puntos ajustados no están en la tabla de formas porque se derivaron por interpolación.

Entonces mi pregunta es: ¿Cómo calculo la ruta más corta entre dos puntos en la red OSM que no están necesariamente en la tabla de formas?

interpolation pgrouting Fezter
fuente
Me parece que estás tratando de resolver el problema del vendedor ambulante . En ese caso, el camino más eficiente sería usar un algoritmo TSP ...
ntg

Respuestas:

3

Resolvimos el mismo problema con aristas y vértices temporales. Ajustamos nuestros cables GPS a un borde 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 de esto un nuevo vértice v_tmp:

line_interpolate_point(geom(e), segOffset);

Luego dividimos nuestro borde e1 en dos nuevos bordes e_tmp1 de v1 a v_tmp y e_tmp2 de v_tmp a v2. (Podría necesitar dividirlo en 4 extremos temporales ...)

Con nuestro objetivo hicimos lo mismo. Luego comenzamos a explorar con nuestros nuevos vértices v_tmp_source, v_tmp_dest y eso es todo.

Axel Zingsem
fuente
2

Me puse en contacto con los nodos más cercanos, utilicé pgrouting para encontrar la ruta entre estos nodos. Estaba detrás de la distancia total, así que luego agregué las dos distancias punto-nodo.

Tenía un límite superior de lo cerca que debía estar un nodo, para ser aceptable.

La matemática sería más complicada / lenta, pero podría hacer lo mismo para los bordes si estuviera utilizando un algoritmo de pgrouting que funcionara en términos de bordes en lugar de nodos.

winwaed
fuente
(Lo siento, de alguna manera no puedo comentar "winwaed", así que tengo que hacerlo con otra respuesta)> Las matemáticas serían más complicadas / más lentas, pero podrías hacer lo mismo para los bordes si usaras un algoritmo de pgrouting que trabajó en términos de bordes en lugar de nodos. El algoritmo Shooting Star toma bordes en lugar de nodos.
dkastl
Ni el nodo más cercano ni los procedimientos basados ​​en el borde van a funcionar, vea el siguiente ejemplo. dl.dropbox.com/u/11502389/Screenshot2.png Las líneas azules son las formas en que se activan los puntos verdes.
1

Su problema me recuerda a un caso similar, que tuvimos que resolver hace algunos años: alguien está dibujando un camino (cadena lineal) en la parte superior de un mapa ráster y tuvimos que hacer coincidir este camino con la red de carreteras subyacente.

Esto parece ser similar a sus puntos GPS rojos. E igual que usted, asumimos que podemos buscar el camino más corto entre estos puntos.

Debido a que esto fue hace mucho tiempo, ya no recuerdo detalles. Pero publicamos las funciones en "matching.sql", que ya forma parte de pgRouting. Sin embargo, no hay documentación. Lo siento por eso. Pero tal vez leer la fuente SQL le da una idea de cómo funciona: https://github.com/pgRouting/pgrouting/blob/master/core/sql/matching.sql

dkastl
fuente
Usar los nodos más cercanos no funciona, considere el siguiente ejemplo.
Esta función de coincidencia que menciono hace una combinación de coincidencia con nodos y segmentos de carretera. Depende de qué tan cerca esté su punto GPS de un nodo. Si está muy cerca de un cruce, su punto GPS podría estar más cerca de un borde, al que en realidad no debería asignársele.
dkastl