Identificación de segmentos de rutas comunes desde las pistas de GPS

Question

Digamos que tengo un montón de pistas de GPS grabadas. Algunos son de viajes repetidos por la misma ruta, algunos son de rutas completamente únicas, y algunos son rutas distintas pero tienen algunos segmentos en común.

Teniendo en cuenta todos estos datos, quiero:

1. identificar los repetidos viajes por la misma ruta
2. identificar los segmentos que son compartidos por múltiples rutas

supongo 1 es realmente una caso especial de 2.

Para dar un ejemplo concreto: suponga que tiene pistas de GPS diarias de una gran cantidad de personas que viajan en bicicleta. Sería interesante extraer de estos datos los corredores de transporte en bicicleta más populares basados ​​en la conducción real en lugar de los mapas de ciclismo producidos por los gobiernos locales.

¿Existen algoritmos publicados para hacer esto? ¿Cómo trabajan? Sugerencias para documentos y/o códigos muy apreciados.

Answer 1

Puede utilizar el histograma 3D para encontrar los puntos más visitados en el mapa. Usando eso puedes derivar los caminos más usados.

Detalle: mantener un recuento de matriz 2D e inicializarlo en 0, X [i, j] = 0. Para cada pista, incremente X [i, j] s en la ruta. Una vez que haya procesado todas las pistas, limite este umbral de matriz a mínimo (¿cuál es el número mínimo de pistas para que sea un viaje repetido?).

Algunos detalles prácticos: suponiendo que tiene un conjunto de puntos a través de los cuales va la ruta. Puede encontrar el conjunto de puntos en la ruta entre dos de esos puntos con http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm. Es posible que desee dibujar una "línea más gruesa" para tener en cuenta la naturaleza ruidosa de los datos.