La première partie du problème description
1.1 Tâches spécifiques
Cette tâche d'emploi est la compression de la trajectoire. Compte tenu d'un fichier d'enregistrement de données GPS, chaque enregistrement contient deux champs de coordonnées, la longitude et la dimension. Tous les enregistrements ont des coordonnées de latitude et de longitude pour former une trajectoire. Il est nécessaire d'utiliser un algorithme de compression approprié afin que l'erreur de distance de la trajectoire comprimée soit inférieure à 30 m.
1.2 Entrée du programme
L'entrée de ce programme est un fichier d'enregistrement de données GPS.
1.3 Sortie de données
Le formulaire de sortie est un fichier, comprenant trois parties, la séquence d'ID et les coordonnées du point comprimé, le nombre de points, l'erreur de distance moyenne et le taux de compression.
Réponses à la deuxième partie
Selon la description du problème, nous résolvons le problème et la résolution de problèmes est divisée en étapes suivantes:
2.1 Prétraitement des données
Cette entrée de programme est un fichier d'enregistrements de données GPS, avec un total de 3150 lignes d'enregistrements, et chaque ligne d'enregistrements est divisée en plusieurs champs. Selon la question, nous n'avons qu'à prêter attention aux champs de coordonnées de longitude et de latitude. Certains enregistrements du fichier de données d'origine sont illustrés à la figure 2.1:
Figure 2.1 Diagramme schématique des enregistrements partiels du fichier de données d'origine
Comme le montre la figure 2.1, le format de stockage des données de champ de coordonnées de latitude et de longitude dans chaque enregistrement dans le fichier de données d'origine est une méthode d'expression de coordonnées GPS typique, c'est-à-dire que le format de division de diplôme, le formulaire est DDDMM.MMMMMM, où DDD représente le degré, MM.MMMMM représente la fraction, le point décimal représente la partie de la fraction de la fraction et le point décimal représente la partie de la fraction de la fraction, et le point décortiqué; Dans ce prétraitement des données, afin de faciliter le calcul de la distance entre les deux points de coordonnées suivants, nous devons convertir les données de coordonnées de latitude et de longitude dans le format de division de degré en forme de degré, la méthode de conversion est DDD + mmmmm / 60. Ici, nous conservons les 6 chiffres après le point décimal et la forme convertie est ddd.xxxxxx.
Nous prenons les coordonnées de latitude et de longitude dans le premier enregistrement (11628.2491, 3955.6535) par exemple. Le résultat de la conversion est (116.470818, 39.927558). Les coordonnées de latitude et de longitude dans tous les enregistrements sont effectuées en utilisant la méthode, et un ID peut être généré pour chaque point de coordonnée converti et identifié de manière unique. Après la compression, nous n'avons qu'à produire les ID de tous les points réservés.
2.2 Algorithme de compression de trajectoire de Douglas-Peucker
Les algorithmes de compression de trajectoire sont divisés en deux catégories, à savoir la compression sans perte et la compression avec perte. Les algorithmes de compression sans perte incluent principalement le codage de Huffman, et les algorithmes de compression avec perte sont divisés en méthode de traitement par lots et méthode de compression de données en ligne. La méthode de traitement par lots comprend l'algorithme DP (Douglas-Peucker), l'algorithme TD-T-T-TR (Time-Ratio de haut en bas) et l'algorithme Bellman. Les méthodes de compression de données en ligne incluent les fenêtres coulissantes, les fenêtres ouvertes, les méthodes de sécurité basées sur la zone, etc.
En raison du temps limité, pour cette compression de trajectoire, nous avons décidé d'utiliser un algorithme DP relativement simple.
Les étapes de l'algorithme DP sont les suivantes:
(1) connecter une ligne droite AB entre deux points A et B au début et à la fin de la courbe, et la ligne droite est la corde de la courbe;
(2) Traverser tous les autres points de la courbe, trouver la distance de chaque point à la ligne droite AB, trouver le point C avec la distance maximale et enregistrer la distance maximale comme Dmax;
(3) Comparez la distance Dmax avec la taille Dmax de seuil prédéfinie. Si dmax <dmax, la ligne droite AB est utilisée comme approximation du segment de courbe et le segment de courbe est traité;
(4) Si dmax> = dmax, le point C divise la courbe AB en deux sections AC et CB, et effectue (1) à (3) les étapes de ces deux sections respectivement;
(5) Lorsque toutes les courbes sont traitées, la polyligne formée par chaque point de segmentation est connectée à son tour, c'est-à-dire le chemin de la courbe d'origine.
2.3 La distance du point à la ligne
Dans l'algorithme DP, nous devons trouver la distance d'un point à une ligne droite. Cette distance fait référence à la distance verticale en forme d'euro, c'est-à-dire la distance d du point C à l'extérieur de la ligne droite AB à la ligne AB. Ici, les points A, B et C sont toutes des coordonnées de latitude et de longitude; Nous utilisons la méthode de la surface égale des triangles pour trouver la distance d. La méthode spécifique est: les points A, B et C forment un triangle. Il existe deux façons de trouver la zone de ce triangle, à savoir la méthode ordinaire (hauteur X inférieure / 2) et la formule Helen. La formule Helen est la suivante:
Supposons qu'il y ait un triangle avec des longueurs latérales A, B et C respectivement. La zone S du triangle peut être obtenue à partir de la formule suivante:
où p est la moitié de la circonférence:
Nous pouvons trouver la zone du triangle à travers la formule Helen, puis nous pouvons trouver la taille de la hauteur, où la hauteur est la distance d. Pour utiliser la formule Helen, vous devez trouver la distance entre trois points A, B et C. La formule de distance est donnée par l'enseignant, et vous pouvez appeler directement la fonction de distance.
Remarque: Après avoir trouvé la distance, ajoutez la valeur absolue pour empêcher la distance d'être négative.
2.4 Résoudre l'erreur moyenne
L'erreur moyenne fait référence à la valeur obtenue en divisant la somme des distances des points ignorés pendant la compression au segment de ligne correspondant par le nombre total de points.
2.5 Solution au taux de compression
La formule de calcul du rapport de compression est la suivante:
2.6 Génération de fichiers de résultats de données
Après le traitement et le calcul ci-dessus, nous écrivons l'ID des points restants après compression et le nombre de points, l'erreur de distance moyenne, le taux de compression et d'autres paramètres dans le fichier de résultat final, et la réponse à la question est remplie.
Implémentation du code de la partie 3
Ce programme est écrit en langue java, avec l'environnement de développement de l'idée Intellij 14.0.2. Le code est divisé en deux classes. L'un est la classe Enpoint, qui est utilisée pour enregistrer les informations de la latitude et le point de longitude, et l'autre est la classe TrajectoryCompressionMain, qui est utilisée pour écrire des fonctions telles que le traitement des données, l'algorithme DP, la distance point à ligne et l'erreur moyenne.
3.1 Processus de procédure générale
L'ensemble du flux du programme comprend principalement les étapes suivantes:
(1) Définissez le tableau Array ARRAYLIST et l'objet de fichier, parmi lesquels il existe trois objets Array Array Array, à savoir le tableau de coordonnées de latitude et de longitude d'origine pgpsarryinit, le tableau des coordonnées ponctuelles filtrées pgpsarrayfilter et le tableau de coordonnées ponctuels filtrée et triée pgpsarrayfilterort; Il y a cinq objets de fichier, à savoir l'objet de fichier de données d'origine FGPS, l'objet de fichier de données de résultat compressé OGPS, le fichier de données finitgpspoint qui maintient les points de coordonnées de latitude et de longitude d'origine converti, les fichiers de test de simulation ftesttinpoint et ftestFilterPoint.
(2) Obtenez les coordonnées du point d'origine et écrivez-les dans le fichier, y compris principalement deux opérations: lire le fichier et écrire le fichier;
(3) effectuer une compression de trajectoire;
(4) trier les coordonnées compressées de latitude et de longitude;
(5) générer des fichiers de test de simulation et utiliser des outils de langage R pour dessiner des graphiques pour obtenir le résultat final;
(6) Trouvez l'erreur moyenne et le taux de compression, l'erreur moyenne est obtenue par une fonction et le taux de compression est directement calculé;
(7) rédiger le résultat final dans le fichier de résultat, y compris l'ID de point filtré, le nombre de points, l'erreur moyenne et le taux de compression;
3.2 Code d'implémentation spécifique
(1) enpoint.java
Package CC.Xidian.main; Importer java.text.decimalformat; / *** créé par Hadoop le 2015/12/20. * / public class Enpoint implémente comparable <enpoint> {public int id; // point idpublic double pe; // longitude public double pn; // dimension publie enpoint () {} // vide Constructeur public tostring () {// devimal new decimalformat ("0,000000"); return this.id + "#" + this.pn + "," + this.pe;} public String getTestString () {decimalformat df = new decimalformat ("0.0000000"); return df.format (this.pn) + "," + df.format (this.pe);} public String getResultString () {decimalformat df = new Decimalformat ("0.000000"); return this.id + "#" + df.format (this.pn) + "," + df.format (this.pe);} @ overdepublic int compareto (enpoint autre) {if (this.id <autre) return -1; else if (this.id> autre.id) return1; elsereturn0;}}(2) trajectorycompressionmain.java
Package cc.xidian.main; import java.io. *; import java.text.decimalformat; import java.util. *; import java.util.list; / *** créé par Hadoop sur 2015/12/19. * / Public Class TrajectoryCompressionMain {public static vide main (String [] args) lots Exception{//------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pGPSArrayInit = new ArrayList <Nepoint> (); // Enregistrement d'origine Record de latitude et longitude Coordonnée Array ArrayList <Nepoint> PGPSARAYFILTER = NOUVEAU ARRAYLIST <NOPORT> (); // Filtory Latitude et Longitude Coordonnées Array Array <EnPoint> PGPSARAYFILTORT = NOUVEAU ARRAYLIST <enPoint Fgus = NEWTORDE et TOLED FILTORDE et TRIDÉE COORDINE CORARDINE CORARDE CORARDE FGPES = NEWTORDET ET SORENDE Fichier ("2007-10-14-gps.log"); // Fichier de données d'origine Fichier Fichier OGPS = nouveau fichier ("2015-20-25-gps-reult.log"); // Fichier de données sur les résultats du résultat // maintient le fichier de données de latitude d'origine et de longitude après avoir converti en degrés, en gardant le formati Numéros à 6 chiffres après le fichier de point décimal FinitGPSpoint = nouveau fichier ("2007-10-14-gps-enpoint.log"); // maintient le fichier de données converti du fichier de latitude et de longitude d'origine après le fichier converti ftestinItpoint = nouveau fichier ("2007-10-14-gps-in-itestpoint. ftestFilterPoint = nouveau fichier ("2015-12-25-gps-filterTestPoint.log"); // utilisé pour le fichier de données de point de coordonnées de latitude et de longitude après simulation//------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- PGPSArrayInit); // Écrivez les données de point de latitude et de longitude converties dans le fichier System.out.println (pgpsarrayinit.size ()); // Sortie du nombre de points de latitude et de longitude d'origine coordinates//---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 30.0; // Définissez le seuil d'erreur de distance maximale pgpsarrayfilter.add (pgpsarrayinit.get (0)); // obtenez les coordonnées du premier point de latitude et de longitude d'origine et les ajoutez au tableau filtré pgpsarrayFilter.add (pgpsarrayInit.get (pgpsarrayInit.Size () - 1); point de latitude et longitude original et ajoutez-les au tableau filtré Enpoint [] enpinit = new Enpoint [pgpsarrayinit.size ()]; // utilisez un tableau de points pour recevoir toutes les coordonnées ponctuelles pour l'itérateur de compression ultérieur = iinit.next (); jj ++;} // Copiez les coordonnées du point de ArrayList dans le tableau de points int start = 0; // Démarrer l'indice int fin = pgpsArrayInit.size () - 1; // End AbSLICT TRAJCOMPRESSC (ENPINIT, PGPSARAYFILTER, START, END, DMAX); // DP ALGORITHMMM System.out.println (pgpsArrayFilter.Size ()); // Sortie compressée Points // ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Enpoint [pgpsArrayFilter.size ()]; // Utilisez un tableau de points pour recevoir les coordonnées du point filtré, pour le tri suivant Iterator <Nepoint> if = pgpsArrayFilter.Iterator (); int i = 0; while (if.hasnext ()) {enpfilter [i] = if.next (); i ++; Les arrays de points Point Arrays.sort (enpfilter); // tri pour (int j = 0; j <enpfilter.length; j ++) {pgpsarrayfilter tableau}//------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- PGPSArrayFiltersort); // Écrivez les points de données de latitude filtrée et de longitude dans le fichier de simulation, le format est "longitude, dimension" // -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- getMeandisterRor (pgpsArrayInit, pgpsArrayFiltersort); // Trouvez l'erreur moyenne System.out.println (Mderror); // ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- (double) pgpsArrayFilter.size () / pgpsArrayInit.size () * 100; // Trouvez le taux de compression System.out.println (Crate); // ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- et rapport de compression WriteFilterPointTofile (OGPS, PGPSArrayFiltersort, Mderror, Crate); // ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- @param fgps: fichier de données source * @return pgpsArrayInit: return ArrayList Array qui enregistre toutes les coordonnées de point * @throws exception * / public static ArrayList <Nepoint> GEtenpointFromfile (fichier fgps) lance l'exception {ArrayList <Depoint> pgpsArray = new ArrayList <Nepoint> (); if (fgps.exists () && fgps.isfile ()) {inputStreamReader read = new InputStreamReader (new FileInputStream (FGPS)); BufferedReader Breater = New BufferedReader (Read); String Str; String [] STRGPS; int i = 0; while ((strydater Breader.Readline ())! = null) {strgps = str.split ("); enpoint p = new enpoint (); p.id = i; i ++; p.pe = (dfTodu (strgps [3])); p.pn = (dftodu (strgps [5])); pgpsAray.add (p);} areau de parine.close (); PGPPSARray;} / *** Fonction Fonction: Écrivez les coordonnées de latitude et de longitude, l'erreur de distance moyenne et le rapport de compression du point filtré au fichier de résultat * @param outgpsfile: fichier de résultat * @param pgpspointfilter: point filtré * @param mderror: erreur de distance moyenne * @param crate: compression ratio * @throws exception * OutGPSFile, ArrayList <Nepoint> PGPSPointFilter, Double Mderror, Double Crate) lève Exception {Iterator <Neppoint> iFilter = PGPSPointFilter.iterator (); RandomAccessFile Rfilter = NOUVEAU RABLADACCESSFILE (OUTGPSFILE, "RW"); sfilter = p.getResultString () + "/ n"; byte [] bfilter = sfilter.getbytes (); rfilter.write (bfilter);} string strmc = "#" + Integer.ToString (pgpspointFilter.size ()) + "," + double.toString (Mderror) + "," + double.tostring (Crate) + "%" + "#" + "/ n"; byte [] bmc = strmc.getBytes (); rfilter.write (bmc); rfilter.close ();} / *** Fonction Fonction: Enregistrez les points de données de latitude et de longitude d'origine convertis dans un fichier * @param outgpsfile * @param pgpspointfilter * @throws exception * / public static writeInitpointfile (fichier outgpsfile, avallist <appoint> pgpspointFilter) lève une exception {iterator <enpoint> ifilter = pgpspointFilter.Iterator (); randomaccessfile rfilter = new randomaccessfile (outgpsfile, "rw"); while (ifilter.hasnext ()) {enpoint p = ifilter.next (); string sfilter = p.tostring () + "" bfilter = sfilter.getBytes (); rfilter.write (bfilter);} rfilter.close ();} / *** Fonction Fonction: Écrire des données de coordonnées de point de latitude et de longitude dans le tableau dans le fichier de test pour les tests Visual * @Param OutGPSFile: Fichier Objectif * @param pgpspoint WriteTestPointToFile (fichier outgpsfile, arrayList <Nepoint> pgpspointFilter) lève l'exception {iterator <npoint> ifilter = pgpspointFilter.iterator (); randomaccessfile rfilter = new randomaccessfile (outgpsfile, "rw"); sfilter = p.getTestString () + "/ n"; byte [] bfilter = sfilter.getBytes (); rfilter.write (bfilter);} rfilter.close ();} / *** fonction de la fonction: converti brute la latitude brute et les données de coordonnées longues * @Reaux de degrés: les données de la longueur d'origine et les coordonnées longues et les coordonnées de longue durée correspondant * / public 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 (strepn) / 60; return d;} / *** fonction function: weep six places de décoble * à double; @param d: le double numéro d'origine * @return renvoie le double numéro converti * / public static double getPointSix (double d) {decimalformat df = new Decimalformat ("0,000000"); (trouver en utilisant la formule Helen). Math.abs(geoDist(pA, pX));double c = Math.abs(geoDist(pB, pX));double p = (a+b+c)/2.0;double s = Math.sqrt(Math.abs(p*(pa)*(pb)*(pc)));double d = s*2.0/a;return d;}/*** Function function: Use the method given by the teacher to find the distance between two Points de latitude et de longitude qui sont incompréhensibles * @param pa: start Point * @param pb: point final * @return Distance: Distance * / public static double géodist (Enpoint PA, enpoint pb) {double radlat1 = rad (pa.pn); double radlat2 = rad (pb.pn); double delta = rad (pb.pe - pa.pe); 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); double top = math.sqrt (top_1 * top_1 + top_2 * top_2); Math.Sin (Radlat1) * Math.Sin (Radlat2) + Math.cos (Radlat1) * Math.cos (Radlat2) * Math.cos (delta_lon); Double Delta_Sigma = Math.Atan2 (TOP, BAS @return le radian retourné * / public statique double rad (double d) {return d * math.pi / 180.0;} / *** Fonction Fonction: Selon la limite de distance maximale, la trajectoire d'origine est échantillonnée récursive à l'aide de la méthode DP pour obtenir la trajectoire compressée * @Param Enpinit: Conserver la coordination de la latitude d'origine * Array * @param Démarrer: Démarrer l'indice * @param end: Endpoint Indice * @param dmax: Erreur de distance maximale préspécifiée * / public static void trajcompressc (enpoint [] enpinit, ArrayList <Nepoint> enParrayFilter, int start, int fin, double dmax) {if (start <end) {// Récursive condition Double MaxDist = 0; cur_pt = 0; // Indice actuel pour (int i = start + 1; i <end; i ++) {double curdist = disttosegment (enpinit [start], enpinit [end], enpinit [i]); // distance du point actuel au segment de ligne correspondant si (curdist> maxdiste) {maxdist = curdist; cur_pt = i;} Distance maximale et point correspondant de la distance maximale} // Si la distance maximale actuelle est supérieure à l'erreur de distance maximale if (maxDist> = dmax) {enParrayFilter.Add (Enpinit [Cur_PT]); // Ajouter le point actuel dans le point filtré // Désasmettez le processus de ligne d'origine dans deux segments centrés sur le point actuel, et effectuer le traitement de la récursion, le segment de la ligne d'origine dans deux segments centrés sur le point actuel, et effectue le traitement de la récursion respectivement dans les deux segments centrés sur le point actuel, et effectuer le traitement de la Récursion Controw TrajCompressc (enpinit, enparrayfilter, start, cur_pt, dmax); coordonnées * @return: renvoie la distance moyenne * / public static double getmeandisterRor (ArrayList <Nepoint> pgpsArrayInit, ArrayList <Nepoint> pgpsArrayFiltersort) {double 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 (start), pgpsarrayinit.get (fin), pgpsarrayInit.get.get (j));} sumdist / (pgpsArrayInit.Size ()); retour moyendiste;}}Résultats de la procédure de partie IV
4.1 Résultats de sortie du programme
Résultats comprimés:
(1) Nombre total de points: 140 points; (2) Erreur de distance moyenne: 7,943786; (3) Taux de compression: 4,4444%
4.2 Résultats de la simulation
Après compression de trajectoire, nous convertissons les points de coordonnées de latitude et de longitude d'origine en points de coordonnées de latitude et de longitude compressés et filtrés. Nous écrivons ces deux points de coordonnées de données en deux fichiers, puis dessions les trajectoires avant et après la compression en fonction de ces deux fichiers, et les comparons. Sur la base des résultats de comparaison, nous pouvons voir si notre algorithme de compression de trajectoire est efficace. Le résultat de comparaison final est illustré à la figure 4.1:
Résumé de la partie 5
Au cours du processus d'écriture de ce programme, j'ai rencontré divers problèmes et appris beaucoup d'expérience en programmation. Ce qui suit est un résumé des problèmes et des solutions rencontrés, et a finalement présenté des suggestions d'amélioration pour les lacunes du programme.
5.1 Problèmes et solutions rencontrées
Question 1: Problème d'ordre des coordonnées de latitude et de longitude
Solution: Les paramètres de la formule de distance sont que la latitude est à l'avant et la longitude est à l'arrière, et l'ordre des points de coordonnées de latitude et de longitude doit être ajusté.
Question 2: La distance ne peut pas être négative
Solution: Assurez-vous que la distance trouvée ne peut pas être négative, ajoutez une fonction de valeur absolue.
Question 3: Détails de l'implémentation de l'algorithme DP
Solution: j'ai commencé à utiliser ArrayList Array pour résoudre le problème des indices. Il y a eu une énorme erreur lors de la résolution de récursivement. Plus tard, je suis passé à l'utilisation des indices de tableau ordinaires pour la récursivité, et le résultat a été bien meilleur.
5.2 lacunes et perspectives existantes
(1) Lors de l'exécution de la compression de la trajectoire, l'algorithme DP est l'algorithme le plus simple et n'est pas le meilleur. Certains algorithmes avec de bons résultats peuvent être utilisés pour effectuer à nouveau une compression de trajectoire;
(2) Les enregistrements de données de cette expérience sont de 3 150 et la quantité de données n'est pas importante. Que dois-je faire s'il y a 1 milliard de données? Nous pouvons considérer le matériel, la distribution, le prétraitement des données, la segmentation des données et les entrepôts de données avec de bonnes performances.
Ce qui précède est le contenu complet de cet article sur le code détaillé de l'algorithme de Douglas-Peucker pour la programmation Java pour implémenter la compression de la trajectoire. J'espère que ce sera utile à tout le monde. S'il y a des lacunes, veuillez laisser un message pour le signaler. Merci vos amis pour votre soutien pour ce site!