Descripción del problema de la primera parte
1.1 tareas específicas
Esta tarea de trabajo es la compresión de la trayectoria. Dado un archivo de registro de datos GPS, cada registro contiene dos campos de coordenadas, longitud y dimensión. Todos los registros tienen coordenadas de latitud y longitud para formar una trayectoria. Se requiere usar un algoritmo de compresión adecuado para que el error de distancia de la trayectoria comprimida sea inferior a 30 m.
1 1.2 Entrada del programa
La entrada de este programa es un archivo de registro de datos GPS.
1.3 Salida de datos
El formulario de salida es un archivo, que incluye tres partes, la secuencia de identificación y las coordenadas del punto comprimido, el número de puntos, el error de distancia promedio y la tasa de compresión.
Respuestas a la segunda parte
Según la descripción del problema, resolvemos el problema, y la resolución del problema se divide en los siguientes pasos:
2.1 Preprocesamiento de datos
Esta entrada del programa es un archivo de registro de datos GPS, con un total de 3150 líneas de registros, y cada línea de registros se divide en varios campos. Según la pregunta, solo necesitamos prestar atención a los campos coordinados de longitud y latitud. Algunos registros del archivo de datos original se muestran en la Figura 2.1:
Figura 2.1 Diagrama esquemático de registros parciales del archivo de datos original
As shown in Figure 2.1, the storage format of the latitude and longitude coordinate field data in each record in the original data file is a typical GPS coordinate expression method, that is, the degree division format, the form is dddmm.mmmmmm, where ddd represents degree, mm.mmmm represents fraction, the decimal point represents the integer part of the fraction, and the decimal point represents the decimal part of the fraction; En este preprocesamiento de datos, para facilitar el cálculo de la distancia entre los siguientes dos puntos de coordenadas, necesitamos convertir los datos de coordenadas de latitud y longitud en el formato de división de grado en forma de grado, el método de conversión es DDD+mm.mmmm/60. Aquí conservamos los 6 dígitos después del punto decimal, y la forma convertida es ddd.xxxxxx.
Tomamos las coordenadas de latitud y longitud en el primer registro (11628.2491, 3955.6535) como ejemplo. El resultado de conversión es (116.470818, 39.927558). Las coordenadas de latitud y longitud en todos los registros se realizan utilizando el método, y se puede generar una ID para cada punto de coordenada convertido e identificada de manera única. Después de la compresión, solo necesitamos emitir las ID de todos los puntos reservados.
2.2 Algoritmo de compresión de trayectoria de Douglas-Peucker
Los algoritmos de compresión de trayectoria se dividen en dos categorías, a saber, compresión sin pérdidas y compresión con pérdida. Los algoritmos de compresión sin pérdidas incluyen principalmente la codificación de Huffman, y los algoritmos de compresión con pérdida se dividen en el método de procesamiento por lotes y el método de compresión de datos en línea. El método de procesamiento por lotes incluye algoritmo DP (Douglas-Peucker), algoritmo TD-TR (relación de tiempo de arriba hacia abajo) y algoritmo de Bellman. Los métodos de compresión de datos en línea incluyen ventanas deslizantes, ventanas abiertas, métodos seguros basados en área, etc.
Debido al tiempo limitado, para esta compresión de trayectoria, decidimos usar un algoritmo DP relativamente simple.
Los pasos del algoritmo DP son los siguientes:
(1) Conecte una línea recta AB entre dos puntos A y B al comienzo y al final de la curva, y la línea recta es el acorde de la curva;
(2) atraviese todos los demás puntos en la curva, encuentre la distancia desde cada punto hasta la línea recta AB, encuentre el punto C con la distancia máxima y registre la distancia máxima como dmax;
(3) Compare la distancia DMAX con el tamaño de dmax umbral predefinido. Si dmax <dmax, la línea recta AB se usa como la aproximación del segmento de la curva y se procesa el segmento de curva;
(4) Si dmax> = dmax, el punto C divide la curva AB en dos secciones AC y CB, y realiza (1) a (3) pasos de estas dos secciones respectivamente;
(5) Cuando se procesan todas las curvas, la polilínea formada por cada punto de segmentación está conectada a su vez, es decir, la ruta de la curva original.
2.3 La distancia de punto a línea
En el algoritmo DP, necesitamos encontrar la distancia desde un punto a una línea recta. Esta distancia se refiere a la distancia vertical en forma de euro, es decir, la distancia D desde el punto C fuera de la línea recta AB a la línea AB. Aquí, los puntos A, B y C son coordenadas de latitud y longitud; Utilizamos el método de triángulos igual del área para encontrar la distancia d. El método específico es: los puntos A, B y C forman un triángulo. Hay dos formas de encontrar el área de este triángulo, a saber, el método ordinario (altura X de abajo/2) y la fórmula Helen. La fórmula de Helen es la siguiente:
Supongamos que hay un triángulo con longitudes laterales A, B y C respectivamente. El área S del triángulo se puede obtener de la siguiente fórmula:
Donde P es la mitad de la circunferencia:
Podemos encontrar el área del triángulo a través de la fórmula de Helen, y luego podemos encontrar el tamaño de la altura, donde la altura es la distancia d. Para usar la fórmula Helen, debe encontrar la distancia entre tres puntos A, B y C. La fórmula de distancia está dada por el maestro, y puede llamar directamente a la función de distancia.
Nota: Después de encontrar la distancia, agregue el valor absoluto para evitar que la distancia sea negativa.
2.4 Resolver el error promedio
El error promedio se refiere al valor obtenido dividiendo la suma de las distancias de los puntos ignorados durante la compresión al segmento de línea correspondiente por el número total de puntos.
2.5 Solución a la tasa de compresión
La fórmula de cálculo de la relación de compresión es la siguiente:
2.6 Generación de archivos de resultados de datos
Después del procesamiento y el cálculo anteriores, escribimos la ID de los puntos restantes después de la compresión y el número de puntos, el error de distancia promedio, la tasa de compresión y otros parámetros en el archivo de resultados finales, y la respuesta a la pregunta se completa.
Implementación del código de la Parte 3
Este programa está escrito en lenguaje Java, con el entorno de desarrollo de IntelliJ Idea 14.0.2. El código se divide en dos clases. Una es la clase Enpoint, que se utiliza para guardar la información de latitud y longitud, y la otra es la clase TrajectoryCompressionMain, que se utiliza para escribir funciones como el procesamiento de datos, el algoritmo DP, la distancia puntual y el error promedio.
3.1 Proceso de procedimiento general
Todo el flujo del programa incluye principalmente los siguientes pasos:
(1) Defina la matriz de matriz y el objeto de archivo relacionado, entre los cuales hay tres objetos de matriz ArrayList, a saber, la matriz de coordenadas de latitud y longitud original PGPSARRYINIT, la matriz de coordenadas de punto filtrado PGPSArrayFilter Hay cinco objetos de archivo, a saber, los FGP del objeto de archivo de datos original, los OGP de objeto de archivo de datos de resultados comprimidos, el archivo de datos FinitGpsPoint que mantiene los puntos de coordenadas de latitud y longitud originales convertidos, los archivos de prueba de simulación FTestinitPoint y FTestFilterPoint.
(2) Obtenga las coordenadas del punto original y escríbalas en el archivo, principalmente incluyendo dos operaciones: leer el archivo y escribir el archivo;
(3) realizar compresión de trayectoria;
(4) Ordene las coordenadas de latitud y longitud comprimidas;
(5) Genere archivos de prueba de simulación y use herramientas de lenguaje R para dibujar gráficos para obtener el resultado final;
(6) Encuentre el error promedio y la tasa de compresión, el error promedio se obtiene a través de una función y la tasa de compresión se calcula directamente;
(7) Escriba el resultado final en el archivo de resultados, incluido el ID de punto filtrado, el número de puntos, el error promedio y la tasa de compresión;
3.2 Código de implementación específico
(1) enoint.java
paquete cc.xidian.main; import java.text.decimalFormat;/*** creado por Hadoop en 2015/12/20.*/public class enpoint implementa comparable <enpotual> {public int id; // punto idpublic Double pe; // longitude public double pn; // dimension public enpoint () {} // vacío constructor public string tostring () {) {) nuevo decimalFormat ("0.00000000"); devuelve this.id+"#"+this.pn+","+this.pe;} public String getTestString () {decimalFormat df = new DecimalFormat ("0.000000000"); return df.format (this.pn)+","+df.format (this.pe);} public string string string (this.pn)+","+df.Format (this.pe);} public string string string (this.pn)+","+df.Format (this.pe);} public string string string (this.pn)+","+df.Format (this.pe);} public string String String (this.pn)+","+df.Format (this.pe);} getResultString () {DecimalFormat df = new DecimalFormat ("0.00000000"); devuelve this.id+"#"+df.format (this.pn)+","+df.format (this.pe);}@overridePublic inter comparación (enppoint otros) {if (this.id <otro.id) regreso -1; else if (this.id> other.id) return1; Elsereturn0;}}(2) TrajectoryCompressionMain.java
paquete cc.xidian.main; import java.io.*; import java.text.DecimalFormat; import java.util.*; import java.util.list;/*** Creado por Hadoop en 2015/12/19.*/Class de clase public Exception{//------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pGPSArrayInit = new ArrayList <Enpoint> (); // Registro original de la latitud y longitud Matriz ArrayList <NEPOINT> PGPSArrayFilter = new ArrayList <NEPOINT> (); // Latitud filtrada y longitud Coordinada matrice ArrayList <NePoint> PGPSArrayFilterSort = new ArrayList <EnPoint> ();//Longa de matriz filtrada y clasificada y clasificada ARAYININE fGPS = new File("2007-10-14-GPS.log");//Original data file object File oGPS = new File("2015-12-25-GPS-Result.log");//Filtered result data file object//Keep the original latitude and longitude data file after being converted into degrees, keeping the format as "ID#Large and longitude value, latitude value", where the longitude and dimension units are grados, y mantenga los números de 6 dígitos después del archivo de punto decimal finitgpspoint = nuevo archivo ("2007-10-14-gps-enpoint.log"); // Mantenga el archivo de datos convertido de la latitud original y el punto de coordenadas de longitud después del archivo converted ftestinitPoint = nuevo archivo ("2007-10-14-gps-Inittestpoint.log"); // Archivo Archivo ftestFilterPoint = nuevo archivo ("2015-12-25-gps-filtertestpoint.log"); // Utilizado para el archivo de datos de puntos de coordenadas de latitud y longitud filtrados después de simulation//------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pGpSarrayInit); // Escribe los datos convertidos de latitud original y punto de longitud en el sistema de archivos. coordinates//---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 30.0; // Establezca el umbral de error de distancia máxima pgpsArrayFilter.Add (pgpsArrayInit.get (0)); // Obtenga las coordenadas de la primera latitud original y punto de longitud y agrégalos a la matriz filtrada PGPSArrayFilter.add (pGpSArrayInit.get (pGpSarrayInit.size ()-1); Latitud y punto de longitud originales y agrégalos a la matriz filtrada enoint [] enpinit = new Enpoint [pGpSarrayInit.size ()]; // Use una matriz de puntos para recibir todas las coordenadas de puntos para el iterador de compresión posterior <EnpoPoint> iinit = pGpSarrayInit.iterator (); int jj = 0; while (iinit.hasnext ()) {enpinit [jj] = iinit.next (); jj ++;} // Copie las coordenadas del punto en ArrayList en la matriz de puntos int inicio = 0; // Subscript int end = pGpSArrayInit.size ()--1; // End Subscript TrajCompressc (Enpinit, PGPsArrayFilter, Start, End, DMAX); // DP Algoritmo de compresión System.out.println (pgpsArrayFilter.size ()); // Salida de salida comprimida points//---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Enoint [pgpsArrayFilter.size ()]; // use una matriz de puntos para recibir coordenadas de puntos filtrados, para el siguiente iterador de clasificación <NEPOINT> if = pgpsArrayFilter.iterator (); int i = 0; while (if.hasnext ()) {enpfilter [i] = if.next (); i ++;} // Copte a la matriz de puntos de punto. matriz} // --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- PGPSArrayFilterSort); // Escribe los puntos de datos de latitud y longitud filtrados en el archivo de simulación, el formato es "longitud, dimensión" // ----------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------- getMeandisterror (pgpsarrayinit, pgpsarrayfiltersort); // Encuentra el error promedio System.out.println (mderror); // --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------- (doble) pgpsarrayfilter.size ()/pgpsarrayinit.size ()*100; // Encuentra la tasa de compresión System.out.println (cita); // ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------- y relación de compresión WriteFilterPointToFile (OGPS, PGPSArrayFiltersort, Merror, Crate); // ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------- @param fgps: archivo de datos de origen* @return pgpsArrayInit: return arrayList array que guarda todas las coordenadas de puntos* @throws excepción*/public static arrayList <Enpoint> getenpointFile (archivo fgps) lanza la excepción {arrayList <Noint> pgpsArray = newe ArrayList <N enPoint> (); if (fgps.exists () && fgps.isfile ()) {inputStreamReader read = new InputStreamReader (new FileInputStream (FGPS)); BufferedReader Breader = New BufferEdreader (read); String Str; String [] Strgps; int i = 0; str.split ("); enoint p = new Enpoint (); p.id = i; i ++; p.pe = (dftodu (strgps [3])); p.pn = (dftodu (strgps [5])); pgpsarray.add (p);} pan de pan.close ();} return pgpSarray;}/*** función de la función: la función de la lonza y la duración de la larga y longitud distance error, and compression ratio of the filtered point to the result file* @param outGPSFile: result file* @param pGPSPointFilter: filtered point* @param mDerror: average distance error* @param cRate: compression ratio* @throws Exception*/public static void writeFilterPointToFile(File outGPSFile,ArrayList<ENPoint> pGPSPointFilter,double MDERROR, Double Crate) lanza la excepción {iterator <NEPOINT> ifilter = PGPSPointFilter.Iterator (); RandomAccessFile rfilter = new RandomAccessFile (OutgpsFile, "RW"); p.getResultString ()+"/n"; byte [] bfilter = sfilter.getBytes (); rfilter.write (bfilter);} string strmc = "#"+Integer.ToString (pgpsPointFilter.size ())+","+double.ToString (mDerror)+","+double.ToString (cierta)+"%"+"#"+"/n"; byte [] bmc = strmmc.getByTes (); rfilter.write (bmc); rfilter.cleCle (). Función Función: Guarde los puntos de datos de latitud y longitud originales convertidos en un archivo* @param outgpsfile* @param pgpspointfilter* @throws excepción*/public static void writeinitPointToFile (archivo outgpsfile, arrayList <NEnPoint> PGPSPointFilter) Excepción {iterator <NOPOINT> ifilter = PGPSPointfilter (literator (itererer (iterer (iterer (iterer (); - iterere (); iterFilter (); ();) rfilter = new RandomAccessFile (outgpsfile, "rw"); while (ifilter.hasnext ()) {enoint p = ifilter.next (); string sfilter = p.ToString ()+"/n"; byte [] bfilter = sfilter.getBytes (); rfilter.write (bfilter);} rfilter.close ();}/*** Función de función: escriba datos de coordenadas de latitud y punto de longitud en el archivo de prueba en el archivo de prueba para las pruebas visuales* @param outgpsfile: archivo de archivo* @param pgpspointfilter: array de punto* @throws excepción*/pública static static void void void (filefile OUTGPSFILE, ArrayList <Enpoint> PGPSPointFilter) lanza la excepción {iterator <NEPOINT> ifilter = PGPSPointFilter.Iterator (); RandomAccessFile rfilter = new RandomAssFile (OutgpsFile, "RW"); p.gettestString ()+"/n"; byte [] bfilter = sfilter.getBytes (); rfilter.write (bfilter);} rfilter.close ();}/*** function function: converver la latitud sin procesar y los datos de coordenadas de longitud en los degrees* @param str: latitudes originales y longitudes coordenadas* @ @retraso el punto de retorno para los datos de la correspondencia de la correspondencia para los datos de la correspondencia de la correspondencia de los datos de la correspondencia. static double dftodu (string str) {int indexd = str.indexof ('.'); string strm = str.substring (0, indexd-2); string strn = str.substring (indexd-2); double d = double.parsedOuble (strm)+double.ParsedOuble (strn)/60; return d;}/*** función de la función: strm decimal de doble* número*@return return el número doble convertido*/public static double getPointSix (doble d) {decimalFormat df = new DecimalFormat ("0.00000000"); Fórmula). px))); doble c = Math.abs (geodist (pb, px)); doble p = (a+b+c) /2.0;double S = math.sqrt (math.abs (p*(pa)*(pb)*(pc))); doble d = s*2.0/a; return d;}/*** función de función: use el método dado por el maestro para encontrar la distancia entre dos latitud incomprehensible* @param pA: Start point* @param pB: End point* @return distance: Distance*/public static double geoDist(ENPoint pA,ENPoint pB){double radLat1 = Rad(pA.pn);double radLat2 = Rad(pB.pn);double delta_lon = Rad(pB.pe - pA.pe);double top_1 = Math.cos(radLat2) * Math.sin (delta_lon); double top_2 = math.cos (radlat1) * math.sin (radlat2) - math.sin (radlat1) * math.cos (radlat2) * math.cos (delta_lon); doube top = math.sqrt (top_1 * top_1 + top_2 * top_2); doble fondo = math.sin (doube (math.sqrt (top_1 * top_1 + top_2 * top_2); double Bottom = Math.sin (Radlat1) Math.sin (radlat2) + math.cos (radlat1)* math.cos (radlat2)* math.cos (delta_lon); doble delta_sigma = math.atan2 (top, fondo); doble distancia = delta_sigma* 6378137.0; return Distance;}/*** función de la función: ángulo radian* @param d: radian*/public static double rad (doble d) {return d* math.pi/180.0;}/*** Función de función: Según el límite de distancia máxima, la trayectoria de la trayectoria original se muestra recursivamente utilizando el método DP para obtener la trayectoria comprimida* @Param Enpinit: Latitud original y Longitud Coordinate Points COORTA* COORDA* COORDEL COORDELTO: MATIR LA ACORDATIVE DE LA ACORDINACIÓN: LA ACORDATIVA DE LA ACORDINACIÓN: LA LATURA ORIGINAL COORTACIÓN COORDET ARTIVE LA ACORDATIVE: Mantenga el COORDELETRADO DE LA ACORDINATIS: Mantenimiento de la Latitud Original. @Param Start: Start Subscript* @Param End: Endpoint Subscript* @param dmax: Prespecified Máximo Error de distancia*/public static void trajCompressc (enoint [] enpinit, arrayList <Enpoint> enParrayFilter, int intar, int ent, doble dmax) {if (inicio <end) {////recursivo doble maxdist = 0////////////////////MAJATIS = 0; // subíndice actual para (int i = start+1; i <end; i ++) {double curdist = distTosegment (enpinit [start], enpinit [end], enpinit [i]); // Distancia desde el punto actual al segmento de línea correspondiente si (curdist> maxdist) {maxdist = curdist; curdin El punto correspondiente de la distancia máxima} // si la distancia máxima actual es mayor que el error de distancia máxima if (maxDist> = dmax) {enParrayFilter.Add (enpinit [cur_pt]); // Agregar el punto actual en la matriz filtrada // Disensamble el segmento de la línea original en dos segmentos centrados en el punto actual, y realiza un punto recursion respectivamente procesado en el procesamiento de recursos respectivamente el procesamiento de la matriz filtrada respectivamente TrajCompressC (Enpinit, EnparrayFilter, Start, Cur_pt, DMax); Coordenadas* @return: devuelva la distancia promedio*/public static double getMeandisterRor (ArrayList <NOPOIN> PGPSArrayInit, ArrayList <NOPOINT> PGPSArrayFilterSort) {doble sumdist = 0.0; for (int i = 1; i <pgpsarrayfiltersort.size (); i ++) {int start = = pgpsArrayFilterSort.get (i-1) .id; int end = pGpSArrayFilterSort.get (i) .id; for (int j = start+1; j <end; j ++) {sumdist+= DistTosegment (pGpsArrayInit.get (inicio), pGpSpsArrayInit.get (end), pgpsArrayInit.get (J));});} sumdist/(pgpsarrayinit.size ()); return meandist;}}Resultados del procedimiento de la Parte IV
4.1 Resultados de salida del programa
Resultados comprimidos:
(1) Número total de puntos: 140 puntos; (2) error de distancia promedio: 7.943786; (3) Tasa de compresión: 4.4444%
4.2 Resultados de simulación
Después de la compresión de trayectoria, convertimos los puntos de coordenadas de latitud y longitud originales en puntos de coordenadas de latitud y longitud comprimidos y filtrados. Escribimos estos dos puntos coordinamos los datos en dos archivos, y luego dibujamos las trayectorias antes y después de la compresión de acuerdo con estos dos archivos, y los comparamos. Según los resultados de comparación, podemos ver si nuestro algoritmo de compresión de trayectoria es efectivo. El resultado de la comparación final se muestra en la Figura 4.1:
Resumen de la Parte 5
Durante el proceso de escritura de este programa, encontré varios problemas y aprendí mucha experiencia en programación. El siguiente es un resumen de los problemas y soluciones encontrados, y finalmente presenta sugerencias de mejora para las deficiencias del programa.
5.1 Problemas y soluciones encontrados
Pregunta 1: Problema de orden de coordenadas de latitud y longitud
Solución: Los parámetros en la fórmula de distancia son que la latitud está al frente y la longitud está en la parte posterior, y el orden de los puntos coordinados de latitud y longitud debe ajustarse.
Pregunta 2: La distancia no puede ser negativa
Solución: asegúrese de que la distancia encontrada no pueda ser negativa, agregue una función de valor absoluto.
Pregunta 3: Detalles de implementación del algoritmo DP
Solución: comencé a usar ArrayList Array para resolver el problema del subíndice. Hubo un gran error al resolver recursivamente. Más tarde, cambié a usar subíndices de matriz ordinarios para la recursión, y el resultado fue mucho mejor.
5.2 Deficiencias y perspectivas existentes
(1) Al realizar la compresión de trayectoria, el algoritmo DP es el algoritmo más simple y no es el mejor. Algunos algoritmos con buenos resultados se pueden usar para realizar la compresión de trayectoria nuevamente;
(2) Los registros de datos de este experimento son 3.150, y la cantidad de datos no es grande. ¿Qué debo hacer si hay mil millones de datos? Podemos considerar hardware, distribuido, preprocesamiento de datos, segmentación de datos y almacenes de datos con buen rendimiento.
Lo anterior es el contenido completo de este artículo sobre el código detallado del algoritmo Douglas-Peucker para la programación Java para implementar la compresión de trayectoria. Espero que sea útil para todos. Si hay alguna deficiencia, deje un mensaje para señalarlo. ¡Gracias amigos por su apoyo para este sitio!