Descrição do problema da parte um
1.1 Tarefas específicas
Esta tarefa de trabalho é compressão de trajetória. Dado um arquivo de registro de dados GPS, cada registro contém dois campos de coordenadas, longitude e dimensão. Todos os registros têm coordenadas de latitude e longitude para formar uma trajetória. É necessário usar um algoritmo de compressão adequado para que o erro de distância da trajetória compactada seja menor que 30m.
1.2 Entrada do programa
A entrada deste programa é um arquivo de registro de dados GPS.
1.3 Saída de dados
O formulário de saída é um arquivo, incluindo três partes, a sequência de identificação e as coordenadas do ponto comprimido, o número de pontos, o erro médio de distância e a taxa de compressão.
Respostas para a segunda parte
De acordo com a descrição do problema, resolvemos o problema, e a solução de problemas é dividida nas etapas a seguir:
2.1 Pré -processamento de dados
Essa entrada do programa é um arquivo de registro de dados GPS, com um total de 3150 linhas de registros, e cada linha de registros é dividida em vários campos. Segundo a pergunta, precisamos apenas prestar atenção nos campos de longitude e latitude coordenando. Alguns registros do arquivo de dados originais são mostrados na Figura 2.1:
Figura 2.1 Diagrama esquemático de registros parciais do arquivo de dados originais
Como mostrado na Figura 2.1, o formato de armazenamento dos dados de campo de latitude e longitude em cada registro no arquivo de dados original é um método típico de expressão de coordenadas GPS, ou seja, o formato da divisão de graus, o formulário é dddmmmmmmmmmmm, onde o DDD representa o grau, a fração de fração, o que o decimal se refere a fração do parto, a fração do parto, a fração do parto, a fração do parto, a fração do parto, a fração do reprodução de reprodução de reprodução, o que o decimal representa a fração do ddmmmmmmmmmmmmmmmmmmmmmmmmmorl e o ponto de reposição de que o decimal se refere a fração do que o DDD reproduz a fração do parto, a fração do que o decimal é a fração do que o dDD. fração; Nesse pré -processamento deste dados, para facilitar o cálculo da distância entre os próximos dois pontos de coordenadas, precisamos converter os dados de coordenar a latitude e longitude no formato da divisão de graus na forma de grau, o método de conversão é DDD+MMMMMMM/60. Aqui mantemos os 6 dígitos após o ponto decimal, e a forma convertida é ddd.xxxxxx.
Tomamos as coordenadas de latitude e longitude no primeiro registro (11628.2491, 3955.6535) como exemplo. O resultado da conversão é (116.470818, 39.927558). As coordenadas de latitude e longitude em todos os registros são realizadas usando o método, e um ID pode ser gerado para cada ponto de coordenada convertido e identificado exclusivamente. Após a compactação, precisamos produzir apenas os IDs de todos os pontos reservados.
2.2 Algoritmo de compressão de trajetória Douglas-Peucker
Os algoritmos de compressão de trajetória são divididos em duas categorias, a saber, compressão sem perdas e compressão com perdas. Os algoritmos de compressão sem perdas incluem principalmente a codificação de Huffman, e os algoritmos de compressão com perdas são divididos no método de processamento de lote e no método de compactação de dados on -line. O método de processamento em lote inclui o algoritmo DP (Douglas-Peucker), o algoritmo TD-TR (de cima para baixo e tempo) e o algoritmo Bellman. Os métodos de compactação de dados on-line incluem janelas deslizantes, janelas abertas, métodos de área segura, etc.
Devido ao tempo limitado, para essa compactação de trajetória, decidimos usar um algoritmo DP relativamente simples.
As etapas do algoritmo DP são as seguintes:
(1) conectar uma linha reta AB entre dois pontos A e B no início e o final da curva, e a linha reta é o acorde da curva;
(2) atravessar todos os outros pontos na curva, encontre a distância de cada ponto até a linha reta AB, encontre o ponto C com a distância máxima e registre a distância máxima como Dmax;
(3) Compare a distância dmax com o tamanho do DMAX limiar predefinido. Se dmax <dmax, a linha reta AB é usada como a aproximação do segmento de curva e o segmento de curva será processado;
(4) Se dmax> = dmax, o ponto C divide a curva ab em duas seções CA e CB, e executar (1) a (3) etapas dessas duas seções, respectivamente;
(5) Quando todas as curvas são processadas, a polilinha formada por cada ponto de segmentação é conectada por sua vez, ou seja, o caminho da curva original.
2.3 A distância de ponto a linha
No algoritmo DP, precisamos encontrar a distância de um ponto a uma linha reta. Essa distância refere-se à distância vertical do tipo euro, ou seja, a distância d do ponto C fora da linha reta AB da linha AB. Aqui, os pontos A, B e C são coordenadas de latitude e longitude; Usamos o método de área igual de triângulos para encontrar a distância d. O método específico é: os pontos A, B e C formam um triângulo. Existem duas maneiras de encontrar a área deste triângulo, a saber, o método comum (parte inferior x altura/2) e a fórmula Helen. A fórmula Helen é a seguinte:
Suponha que haja um triângulo com comprimentos laterais A, B e C, respectivamente. As áreas do triângulo podem ser obtidas da seguinte fórmula:
onde p é meia circunferência:
Podemos encontrar a área do triângulo através da fórmula Helen e, em seguida, podemos encontrar o tamanho da altura, onde a altura é a distância d. Para usar a fórmula Helen, você deve encontrar a distância entre três pontos A, B e C. A fórmula de distância é dada pelo professor e você pode chamar diretamente a função de distância.
Nota: Depois de encontrar a distância, adicione o valor absoluto para evitar que a distância seja negativa.
2.4 Resolva o erro médio
O erro médio refere -se ao valor obtido dividindo a soma das distâncias dos pontos ignorados durante a compactação para o segmento de linha correspondente pelo número total de pontos.
2.5 Solução para a taxa de compressão
A fórmula de cálculo da taxa de compressão é a seguinte:
2.6 Geração de arquivos de resultado de dados
Após o processamento e cálculo acima, escrevemos o ID dos pontos restantes após a compressão e o número de pontos, erro médio de distância, taxa de compressão e outros parâmetros no arquivo de resultado final e a resposta para a pergunta é concluída.
Parte 3 Implementação de código
Este programa é escrito no idioma Java, com o ambiente de desenvolvimento da Idea Intellij 14.0.2. O código é dividido em duas classes. Uma é a classe de ENPOINT, que é usada para salvar informações de latitude e ponto de longitude, e o outro é a classe trajetória compressiva, que é usada para gravar funções como processamento de dados, algoritmo DP, distância ponto a linha e erro médio.
3.1 Processo de procedimento geral
Todo o fluxo do programa inclui principalmente as seguintes etapas:
(1) Definir o objeto de matriz de Arraylist relacionado e o objeto de arquivo, entre os quais existem três objetos de matriz Arraylist, a saber, a matriz de coordenada de latitude e longitude original, a matriz de coordenadas de longitude, o ponto de coordenado de ponto filtrado coordenada PGPSarrayFilter; Existem cinco objetos de arquivo, a saber, o objeto de arquivo de dados original FGPS, o objeto de arquivo de dados de resultado compactado OGPS, o arquivo de dados FinitGPSpoint que mantém os pontos de coordenada de latitude e longitude originais convertidos, os arquivos de simulação de teste ftestinitpoint e fTestFilterpoint.
(2) Obtenha as coordenadas do ponto original e escreva -as no arquivo, incluindo principalmente duas operações: lendo o arquivo e escrevendo o arquivo;
(3) realizar compressão de trajetória;
(4) Classificar as coordenadas de latitude compactada e ponto de longitude;
(5) gerar arquivos de teste de simulação e usar ferramentas de idioma R para desenhar gráficos para obter o resultado final;
(6) Encontre o erro médio e a taxa de compressão, o erro médio é obtido através de uma função e a taxa de compressão é calculada diretamente;
(7) Escreva o resultado final no arquivo de resultado, incluindo o ID do ponto filtrado, número de pontos, erro médio e taxa de compressão;
3.2 Código de implementação específico
(1) ENPOINT.JAVA
pacote cc.xidian.main; importar java.text.decimalformat;/*** criado por Hadoop em 2015/12/20. df = novo decimalformat ("0,000000"); retorne este.id+"#"+this.pn+","+this.pe;} public string getTeststring () {decimalformat df = new decimalformat ("0,0000000"); retorna df.format (this.pn)+"" getResultString () {decimalFormat df = new DecimalFormat ("0,000000"); retorne este.id+"#"+df.format (this.pn)+","+df.format (this.pe);}@substituição de substituição) (eT) (this.id); outros. caso contrário, se (this.id> outros.id) return1; elsereturn0;}}(2) trajetória compressãoMain.java
Pacote cc.xidian.main; importar java.io. Exceção {// ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------ ArrayList<ENPoint>();//Original record latitude and longitude coordinate array ArrayList<ENPoint> pGPSArrayFilter = new ArrayList<ENPoint>();//Filtered latitude and longitude coordinate array ArrayList<ENPoint> pGPSArrayFilterSort = new ArrayList<ENPoint>();//Filtered and sorted latitude and longitude coordinate array File 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 degrees, and keep the 6-digit numbers after the decimal point File fInitGPSPoint = new File("2007-10-14-GPS-ENPoint.log");//Keep the converted data file of the original latitude and longitude coordinate point after the converted file fTestInitPoint = new File("2007-10-14-GPS-InitTestPoint.log");//Featured original latitude and longitude coordinate point data file File ftestFilterPoint = new File ("2015-12-25-GPS-filterTestpoint.log"); // usado para o arquivo de dados de pontos de latitude e longitude filtrado após simulation//------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pgpsArrayInit); // Escreva os dados de ponto de latitude e longitude originais convertidos no sistema de arquivos.out.println (pgpsarrayinit.size ()); // produzindo o número de latitude original e ponto de longitude coordinates//---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 30.0; // Defina o limite máximo de erro de distância pgpSarrayFilter.add (pgpSarrayinit.get (0)); // Obtenha as coordenadas do primeiro ponto de latitude e longitude original e adicione-as) e adicione a matriz filtrada PGPSArrayIlTer.add (pgPSarrayInit.gets; Latitude original e ponta de longitude e adicione -os ao ponto de matriz filtrado [] enpinit = new ENPOINT [PGPSARRAYINIT.SIZE ()]; // Use uma matriz de pontos para receber todas as coordenadas de ponto para o itepressão subsequente (ITERTER JJJ = 0 {ININIT = PGPSARRATRATET.ItERATATOR (); int JJ = 0 = iinit.Next (); jj ++;} // Copie as coordenadas do ponto no ArrayList na matriz de pontos int start = 0; // Iniciar o subscrito int End = pgpSarrayinit.size ()-1; // end subscript trajCompress (ENPINIT, PGPSPRAIXO, ENCTM, DIGN; System.out.println (pgpSarrayfilter.size ()); // saída compactada points//---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ENPOINT [PGPSARRAYFILTER.SIZE ()]; // Use uma matriz de pontos para receber coordenadas de ponto filtrado, para o seguinte iterador de classificação <NoPoint> if = pgpSarrayfilter.iterator (); int i = 0; while (if.hasnext ()) {enpilter [i] if.next; até a matriz de pontos Array.sort (enpfilter); // classifica para (int j = 0; j <enpfilter.length; j ++) {pgpSarrayfiltersort.add (enpfilter [j]); // escreva os coordenados de ponto classificado em um novo ArrayList variedade}//------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- PGPSARRAYFILTERSORT); // Escreva os pontos de dados de latitude e longitude filtrados no arquivo de simulação, o formato é "longitude, dimensão" // -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- getMeaNDististerRor (PGPSarrayinit, PGPSarrayFiltersort); // Encontre o erro médio System.out.println (mderror); // -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ (duplo) pgpSarrayfilter.size ()/pgpsarrayinit.size ()*100; // Encontre a taxa de compressão System.out.println (Crate); // ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- e taxa de compressão writeFilterPointToFile(oGPS,pGPSArrayFilterSort,mDError,cRate);//----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- @param fgps: arquivo de dados de origem* @return pgpSArrayInit: return ArrayList Array que salva todas as coordenadas de ponto* @throws exceção*/public static ArrayList <NePoint> getenPointFromFile (arquivo FGPS) lança exceção {ArrayList <NePoint> pgpsarray = novo ArrayList <NePoint> (); if (fgps.exists () && fgps.isfile ()) {inputStreamReader Read = new InputStreamReader (new FileInputStream (FGPS)); BufferReader Breader = newBhowReader (read); string string; str.Split ("); ENPOINT P = new ENPOINT (); p.id = i; i ++; p.pe = (dftodu (strgps [3])); p.pn = (dftodu (strgps [5])); PGPSArray.add (p);}} funclose (); Erro de distância e taxa de compactação do ponto filtrado para o arquivo de resultado* @param outgpsfile: arquivo de resultado* @param pgppointfilter: ponto filtrado* @param mderror: erro médio de distância* @param Crate: compressão Razão* @Throws Exception*/public static wroid writeFil mderror, dupla caixa) lança exceção {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 ())+","+duplo.toString (mderror)+"," strmc.getBytes (); rfilter.Write (BMC); rfilter.close ();}/*** Função da função: salve os dados de latitude e longitude originais convertidos em um arquivo* @param outgpsfile* @param pgpSpointfilter* @Throws Exceção*/public static Vorid PGPSpointFilter) lança exceção {iterator <NoPoint> ifilter = PGPSpointFilter.iterator (); RandomAccessFile rfilter = new RandomAccessFile (outgpsFile, "rw"); while (ifilter.hasnext ()) {Enpoint p = ifilter.next.next; p.toString ()+"/n"; byte [] bfilter = sfilter.getBytes (); rfilter.write (bfilter);} rfilter.close ();}/*** função **l: Função de latitude e longitude de longitude Os dados da matriz no arquivo* *** **l @param @param e a latitude outg -outg coordenine dados na matriz no arquivo* Array* @Throws Exception*/public static void WRITETESTIPOTTOFILE (FILE outgpsFile, ArrayList <Noporpo> PGPSpointFilter) lança exceção {iterator <NoPoint> ifilter = PGPSpointFilter.iterator (); RandomAccessFile Rfilter = novo RandomAcssfile (outgpGsg (); while (ifilter.hasNext ()) {Enpoint p = ifilter.Next (); String sfilter = p.getTestString ()+"/n"; byte [] bfilter = sfilter.getbytes (); rfilter.write (funclor);} rfilter.close (); De graus* @param str: coordenadas de latitude e longitude originais* @return: retorne os dados de graduação para o correspondente*/public static duplo dftodu (string str) {int indexd = str.indexOf ('. Double.parsedouble (strm)+duplo.parsedouble (strn)/60; retornar d;}/*** Função: mantenha seis locais decimais de um número duplo* @param d: número duplo original* @return retorna o número duplo convertido*/public static duplo getPointsix (Double d) {decimalformat df = double.parsedouble(df.format(d));}/*** Function function: calculate the distance between the point pX and the straight line determined by point pA and pB using the equal method using the area of the triangle (find using the Helen formula). * @param pA: Start point* @param pB: End point* @param pX: Third point* @return distance: The distance between point pX and the straight line where pA and pB is Localizado*/Public Static Double DistTosEgment (ENPOINT PA, ENPOINT PB, ENPOINT PX) {Double a = Math.abs (geodista (PA, PB)); Double B = Math.abs (geodista (PA, PX); Double C = Math.abs (Geods (pb, px)); Math.sqrt (math.abs (p*(pa)*(pb)*(pc))); duplo d = s*2.0/a; return d;}/*** função função: use o método dado pelo professor para encontrar a distância entre os dois pontos de latitude e a ponta de leturn* @ponte -de -leturn* @param @param pa: start point*@param pb end: pb) {duplo radlat1 = rad (pa.pn); duplo radlat2 = rad (pb.pn); delta_lon duplo = rad (pb.pe - pa.pe); duplo top_1 = math.Cos (radlat2) * math.sin (delta_lon); duplo top_2 = math.coS (radlat2) * math.sin (delta); Math.sin (radlat1) * Math.cos (radlat2) * Math.cos (delta_lon); top duplo = math.sqrt (top_1 * top_1 + top_2 * top_2); inferior) = math.sin (radlat1) * math.sin (radlat2) + math.cos (radlat1) * * Math.cos (delta_lon); duplo delta_sigma = math.atan2 (parte superior, inferior); distância dupla = delta_sigma* 6378137.0; distância de retorno;}/*** função da função: Radian ângulo* @param d: ângulo* @return o radiano retornado*/public static duplo rad (d) Para o limite máximo de distância, a trajetória original é amostrada recursivamente usando o método DP para obter a trajetória compactada* @param enpinit: Latitude e longitude de longitude originais Array* @param ENPARRAYFILTER: Manter o ponto de coordenação do ponto de filtro* @param STRAY: SILTRATEM @PREPRAY ENDIN @PARAM ENPARAM ENPARAM ENPARAM ENPARAM: Final do final do ponto* PENTRATIMATEM: o final do ponto de partida* @PARAM @ParrayFilter: ErrMActrinEnTeMTeMeftrin: TRAJCOMPRESSC VOID ESTÁTICO (ENPOINTE [] ENPINIT, ARRAYLIST <NESPOINT> ENPARRAYFILTER, INT START, INT END, DUPLE DMAX) {se (start <end) {// condição recursiva dupla maxdist = 0; // distância máxima int_pt = 0; distToSegment(enpInit[start],enpInit[end],enpInit[i]);//Distance from the current point to the corresponding line segment if(curDist > maxDist){maxDist = curDist;cur_pt = i;}//Finding the subscript of the maximum distance and the corresponding point of the maximum distance}//If the current maximum distance is greater than the maximum distance error if (maxdist> = dmax) {enparrayFilter.add (enpinit [cur_pt]); // Adicione o ponto de corrente à matriz filtrada // desmontar o segmento de linha original em dois segmentos centrados no ponto atual e executar o processamento de recurso, respectivamente, o início do trujompressc (ENPINIT, a hemoil TrajCompressc (ENPINIT, ENPARRAYFILTER, CUR_PT, END, DMAX);}}}/*** Função Função: Encontre o erro médio de distância* @param pgpSarrayinit: Data Original Point Coordena* @param PGPSArrayFiltersort: Filtrado Data Point Coordinates* @Retor getMeArDististerRor (ArrayList <NoPoint> PGPSArrayInit, ArrayList <Noporpo> pgpSarrayFiltersort) {duplo sumDist = 0.0; para (int i = 1; i <pgpSarrayFiltersort.size (); i ++) {start = PGPSarrayFiltersort.size (); i ++) {start = PGPSarrayFilters. pgpSarrayfiltersort.get (i) .id; para (int j = start+1; j <end; j ++) {sumdist+= disttasegment (pgpSarrayinit.get (start), pgpSarrayInit.get (end), pgPSarrayInit.get (j));}} meios meados meandista;}}Parte IV Resultados do procedimento
4.1 Resultados de saída do programa
Resultados compactados:
(1) número total de pontos: 140 pontos; (2) erro de distância média: 7.943786; (3) Taxa de compressão: 4,4444%
4.2 Resultados da simulação
Após a compressão da trajetória, convertemos os pontos de coordenada de latitude e longitude originais em pontos de coordenadas de latitude e longitude compactados e filtrados. Escrevemos esses dois pontos coordenamos os dados em dois arquivos e, em seguida, desenhamos as trajetórias antes e depois da compactação de acordo com esses dois arquivos e os comparamos. Com base nos resultados da comparação, podemos ver se nosso algoritmo de compressão de trajetória é eficaz. O resultado da comparação final é mostrado na Figura 4.1:
Resumo da Parte 5
Durante o processo de escrita deste programa, encontrei vários problemas e aprendi muita experiência em programação. A seguir, é apresentado um resumo dos problemas e soluções encontradas e, finalmente, apresentam sugestões de melhoria para as deficiências do programa.
5.1 Problemas e soluções encontradas
Pergunta 1: Latitude e Longitude Coordenine Order Issue
Solução: Os parâmetros na fórmula de distância são que a latitude está na frente e a longitude está na parte traseira, e a ordem dos pontos de coordenadas de latitude e longitude precisa ser ajustada.
Pergunta 2: A distância não pode ser negativa
Solução: Verifique se a distância encontrada não pode ser negativa, adicione uma função de valor absoluto.
Pergunta 3: Detalhes da implementação do algoritmo DP
Solução: Comecei a usar a Arraylist Array para resolver o problema do subscrito. Houve um erro enorme ao resolver recursivamente. Mais tarde, mudei para o uso de subscritos de matriz comum para recursão, e o resultado foi muito melhor.
5.2 deficiências e perspectivas existentes
(1) Ao realizar a compressão da trajetória, o algoritmo DP é o algoritmo mais simples e não é o melhor. Alguns algoritmos com bons resultados podem ser usados para realizar a compactação de trajetória novamente;
(2) Os registros de dados deste experimento são 3.150 e a quantidade de dados não é grande. O que devo fazer se houver 1 bilhão de dados? Podemos considerar hardware, distribuído, pré -processamento de dados, segmentação de dados e data warehouses com bom desempenho.
O acima exposto está o conteúdo completo deste artigo sobre o código detalhado do algoritmo Douglas-Peucker para a programação Java para implementar a compactação de trajetória. Espero que seja útil para todos. Se houver alguma falha, deixe uma mensagem para apontá -la. Obrigado amigos pelo seu apoio para este site!