Identificazione dei segmenti di percorso comuni dalle tracce GPS

Question

Dire che ho un sacco di tracce GPS registrate. Alcuni provengono da viaggi ripetuti lungo lo stesso percorso, alcuni provengono da percorsi completamente unici e alcuni sono percorsi distinti ma hanno alcuni segmenti in comune.

Dato tutti questi dati, voglio:

1. identificare i ripetuti viaggi sullo stesso percorso
2. identificare i segmenti che sono condivisi da più percorsi

Suppongo 1 è davvero un caso speciale di 2.

Per fare un esempio concreto: si supponga di avere tracce GPS giornaliere di un gran numero di pendolari di biciclette. Sarebbe interessante estrarre da questi dati i corridoi di pendolarismo più popolari basati sulla guida reale piuttosto che sulle mappe ciclistiche prodotte dalle amministrazioni locali.

Esistono algoritmi pubblicati per questo? Come funzionano? I puntatori alle carte e/o al codice sono molto apprezzati.

Answer 1

È possibile utilizzare l'istogramma 3D per trovare i punti più visitati sulla mappa. Usando questo puoi ricavare i percorsi più usati.

Dettagli: mantenere un conteggio matrice 2D e inizializzarlo su 0, X [i, j] = 0. Per ogni traccia, incrementare X [i, j] s sul percorso. Una volta elaborate tutte le tracce, soglia questa matrice alla soglia minima (qual è il numero minimo di tracce per essere un viaggio ripetuto?).

Alcuni dettagli pratici: Supponendo di avere una serie di punti attraverso cui il percorso va. È possibile trovare il set di punti sul percorso tra due di questi punti con http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm. Potresti voler disegnare una "linea più spessa" per tenere conto della natura rumorosa dei dati.