Pregunta

Tengo varias pistas registradas por un GPS, que de manera más formal pueden describirse como una serie de cadenas de líneas.

Ahora, algunas de las rutas grabadas podrían ser grabaciones de la misma ruta, pero debido a imprecisiones en el sistema GPS, el hecho de que las grabaciones se realizaron en ocasiones separadas y que podrían haber sido grabadas viajando a diferentes velocidades, no lo serán. coinciden perfectamente, pero aun así se ven lo suficientemente cerca cuando un humano los ve en un mapa para determinar que en realidad es la misma ruta que se ha registrado.

Quiero encontrar un algoritmo que calcule la similitud entre dos cadenas de líneas.Se me ocurrieron algunos métodos locales para hacer esto, pero me gustaría saber si se trata de un problema que ya cuenta con buenos algoritmos para resolverlo.

¿Cómo calcularías la similitud, dado que medias similares representan el mismo camino en un mapa?

Editar: Para aquellos que no están seguros de lo que estoy hablando, consulte este enlace para obtener una definición de qué es una cadena de líneas: http://msdn.microsoft.com/en-us/library/bb895372.aspx - Soy no preguntando sobre cadenas de caracteres.

¿Fue útil?

Solución

Calcular el distancia de frechet en cada par de pistas.La distancia se puede utilizar para medir la similitud de sus pistas.

Alerta matemática: Fréchet fue un pionero en el campo de espacio métrico que es relevante para su problema.

Otros consejos

Agregaría un búfer alrededor de la primera línea según el error probable estimado y luego determinaría si la segunda línea encaja completamente dentro del búfer.

Para determinar la "misma ruta", cree el conjunto mínimo de vectores de ruta normalizados, calcule las diferencias de potencia total y compare el total con una medida de calidad.

  1. Normalizar los puntos de ruta GPS en la longitud total del camino,
  2. recorrer los vectores de los caminos juntos, creando un nuevo conjunto de vectores de camino para cada camino basado en el vector más corto en cada punto de ruta,
  3. calcular las diferencias de potencia total entre los puntos finales de cada vector en las rutas normalizadas ponderando la longitud del vector, y
  4. comparar con una medida de calidad.

Ajuste visualmente el poder de las diferencias (comience con, digamos, diferencias al cuadrado) y la medida de calidad (digamos como porcentaje de las diferencias de poder total).Este algoritmo produce una medida continua de calidad de la coincidencia de rutas, así como un resultado binario (¿Son las rutas iguales?)

Paul Tomblin dijo:Agregaría un búfer alrededor de la primera línea en función del error probable estimado y luego determinaría si la segunda línea se ajusta completamente dentro del búfer.

Puede modificar el algoritmo a medida que se comparan los puntos finales del vector normalizado.Podría determinar si alguna diferencia de punto final estaba por encima de cierto tamaño (implementando la idea del búfer de Paul) o tal vez, si los puntos finales estaban fuera del "búfer", usar ese hecho para ignorar esa diferencia de punto final, permitiendo una comparación. ignorando los viajes secundarios.

Podrías caminar a lo largo de cada punto (Pa) de LineString A y medir la distancia desde Pa hasta el segmento de línea más cercano de LineString B, promediando cada una de estas distancias.

Este no es un método rápido ni perfecto, pero debería poder dar un número útil y es bastante rápido de implementar.

¿Las cadenas de líneas comienzan y terminan en puntos similares o tienen extensiones muy diferentes?

Si considera que una cadena de una sola línea es una secuencia de puntos [x,y] (o puntos [x,y,z]), entonces podría calcular la similitud entre cada par de cadenas de líneas usando el Needleman-Wunsch algoritmo.Como se describe en el artículo de Wikipedia al que se hace referencia, el algoritmo Needleman-Wunsch requiere una "matriz de similitud" que define la distancia entre un par de puntos.Sin embargo, sería fácil utilizar una función en lugar de una matriz.En su caso, simplemente podría usar el 2D. distancia euclidiana función (o una función euclidiana 3D si sus puntos tienen elevación) para proporcionar la distancia entre cada par de puntos.

De hecho, estoy del lado de la persona (Aaron F) que dijo que usted podría estar interesado en el problema de la distancia de Levenshtein (y citó este).Su respuesta me parece la mejor hasta el momento.

Más específicamente, la distancia de Levenshtein (también llamada distancia de edición), no mide estrictamente la distancia carácter por carácter, pero también permite realizar inserciones y eliminaciones.El mejor algoritmo para esta medida de distancia se puede calcular en tiempo cuadrático (bastante lento si las cadenas son largas), pero los biólogos computacionales tienen heurísticas bastante buenas para esto, que podrían ser de su interés por sí solas.Verificar EXPLOSIÓN y FASTA.

En tu problema, parece que estás lidiando con diferencias entre cadenas de números y te preocupas por los números.Si proporciona más información, es posible que pueda dirigirlo a la variante correcta de BLAST/FASTA/etc para sus propósitos.En cualquier caso, podría considerar adaptar BLAST y FASTA a sus necesidades.Son bastante simples.

1: http://en.wikipedia.org/wiki/Levenshtein_distance, http://www.nist.gov/dads/HTML/Levenshtein.html

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top