Часть первой описание проблемы
1.1 Конкретные задачи
Эта задача - сжатие траектории. Учитывая файл записи данных GPS, каждая запись содержит два поля координат: долгота и измерение. Все записи имеют координаты широты и долготы, чтобы сформировать траекторию. Требуется использовать подходящий алгоритм сжатия, чтобы ошибка расстояния сжатой траектории составляет менее 30 м.
1.2 Ввод программы
Ввод этой программы представляет собой файл записи данных GPS.
1.3 Вывод данных
Выходная форма представляет собой файл, включая три части, последовательность идентификатора и координаты сжатой точки, количество точек, средняя ошибка расстояния и скорость сжатия.
Ответы на вторую часть
Согласно описанию проблемы, мы решаем проблему, и решение проблем делится на следующие шаги:
2.1 Предварительная обработка данных
Этот ввод программы представляет собой файл записи данных GPS, в общей сложности 3150 строк записей, и каждая строка записей разделена на несколько полей. Согласно вопросу, нам нужно только обратить внимание на области долготы и широты. Некоторые записи исходного файла данных показаны на рисунке 2.1:
Рисунок 2.1 Схематическая схема частичных записей исходного файла данных
Как показано на рисунке 2.1, формат хранения данных поля широты и координат долготы в каждой записи в исходном файле данных представляет собой типичный метод выражения координат GPS, то есть формат деления степени, форма - DDDMM.MMMMMM, где DDD представляет степень, мммммммммм, представляет фракцию, децимальная точка представляет фракционную партию; и децимальная точка; В этой предварительной обработке данных, чтобы облегчить расчет расстояния между следующими двумя точками координат, нам необходимо преобразовать данные о широте и долготе координат в формате деления степени в форму степени, метод преобразования составляет DDD+ммммммм/60. Здесь мы сохраняем 6 цифр после десятичной точки, а преобразованная форма - ddd.xxxxxx.
В первой записи мы принимаем координаты широты и долготы в первой записи (11628.2491, 3955.6535). Результат преобразования (116,470818, 39,927558). Координаты широты и долготы во всех записях выполняются с использованием метода, и идентификатор может быть сгенерирован для каждой конвертированной точки координат и уникально идентифицированным. После сжатия нам нужно только вывести идентификаторы всех зарезервированных точек.
2.2 Алгоритм сжатия траектории Дугласа-Пейкера
Алгоритмы сжатия траектории делятся на две категории, а именно сжатие без потерь и сжатие потерь. Алгоритмы сжатия без потерь в основном включают в себя кодирование Хаффмана, а алгоритмы сжатия потерь делятся на метод пакетной обработки и метод сжатия данных в Интернете. Метод пакетной обработки включает алгоритм DP (Douglas-Pucker), алгоритм TD-TR (сверху вниз) и алгоритм Bellman. Методы сжатия данных в Интернете включают скользящие окна, открытые окна, безопасные методы, основанные на зонах и т. Д.
В связи с ограниченным временем для этого сжатия траектории мы решили использовать относительно простой алгоритм DP.
Шаги алгоритма DP следующие:
(1) Подключите прямую линию AB между двумя точками A и B в начале и конце кривой, а прямая линия является аккордом кривой;
(2) Переверните все другие точки на кривой, найдите расстояние от каждой точки до прямой линии AB, найдите точку C с максимальным расстоянием и запишите максимальное расстояние как DMAX;
(3) Сравните расстояние DMAX с предопределенным порогом DMAX. Если DMAX <dmax, AB прямой линии используется в качестве приближения сегмента кривой и обрабатывается сегмент кривой;
(4) Если dmax> = dmax, точка C делит кривую AB на две части AC и CB и выполняет (1) на (3) шаги этих двух разделов соответственно;
(5) Когда все кривые обрабатываются, полилина, образованная каждой точкой сегментации, связана по очереди, то есть путь исходной кривой.
2.3 Расстояние от точки до линии
В алгоритме DP нам нужно найти расстояние от точки до прямой линии. Это расстояние относится к вертикальному евро-подобному расстоянию, то есть расстояние D от точки C за пределами прямой линии до линии AB. Здесь, точки A, B и C являются координатами широты и долготы; Мы используем метод треугольников равной области, чтобы найти расстояние d. Конкретный метод: точки A, B и C образуют треугольник. Есть два способа найти область этого треугольника, а именно обычный метод (нижний x высота/2) и формула Хелен. Формула Елена выглядит следующим образом:
Предположим, есть треугольник с боковой длиной A, B и C соответственно. Площадь S треугольника может быть получена из следующей формулы:
где P - наполовину окружность:
Мы можем найти область треугольника через формулу Елена, и тогда мы сможем найти размер высоты, где высота - расстояние d. Чтобы использовать формулу Хелен, вы должны найти расстояние между тремя точками A, B и C. Формула расстояния определяется учителем, и вы можете напрямую вызвать функцию расстояния.
ПРИМЕЧАНИЕ. После поиска расстояния добавьте абсолютное значение, чтобы не было отрицательного расстояния.
2.4 Решите среднюю ошибку
Средняя ошибка относится к значению, полученному путем деления суммы расстояний от точек, игнорируемых во время сжатия на соответствующий сегмент линии на общее количество точек.
2.5 Решение для скорости сжатия
Формула расчета коэффициента сжатия выглядит следующим образом:
2.6 Генерация файлов результатов данных
После вышеуказанной обработки и расчета мы записываем идентификатор оставшихся точек после сжатия и количество точек, средней ошибки расстояния, скорости сжатия и других параметров в файл конечного результата, и ответ на вопрос завершен.
Реализация кода части 3
Эта программа написана на Java Language, с средой развития INTELLIJ IDEA 14.0.2. Код разделен на два класса. Одним из них является класс Enpoint, который используется для сохранения информации о широте и точки долготы, а другой-класс TrauceoryCompressionMain, который используется для написания таких функций, как обработка данных, алгоритм DP, расстояние точечного до линии и средняя ошибка.
3.1 Общий процесс процедуры
Весь поток программы в основном включает в себя следующие шаги:
(1) Определите соответствующий объект ArrayList Array и File, среди которых есть три объекта ArrayList Array, а именно первоначальный массив координат широты и долготы PGPSArryinit, отфильтрованная координата точек ArrayFiltersort и отфильтрованная и сортированная координат точек PgpsArrayFilterSort; Существует пять файловых объектов, а именно исходный объект файла данных FGPS, объект файла данных сжатого результата OGP, финал файла данных, который поддерживает конвертированные исходные точки широты и координат долготы, файлы тестирования моделирования FtestinitPoint и ftestFilterPoint.
(2) Получить координаты исходной точки и написать их в файл, в основном включая две операции: чтение файла и написание файла;
(3) выполнить сжатие траектории;
(4) сортируют координаты сжатой широты и точки долготы;
(5) Сгенерировать файлы тестирования моделирования и использовать R Language Tools для рисования графики для получения конечного результата;
(6) Найти среднюю ошибку и скорость сжатия, средняя ошибка получается посредством функции, и скорость сжатия напрямую рассчитывается;
(7) запишите конечный результат в файл результата, включая идентификатор отфильтрованной точки, количество точек, среднюю ошибку и скорость сжатия;
3.2 Конкретный код реализации
(1) Enpoint.java
Пакет cc.xidian.main; import java.text.decimalformat;/*** Создан Hadoop на 2015/12/20.*/Public Class Enpoint реализует сопоставимые <enpoint> {public int id; // point idpublic double pe; // public public double pn; // dimension public enpoint () {} // well public string strestring strestring strestring inpublic/{} // well public string strestring () {} // wylous public string strestring (). df = new DecimalFormat ("0,000000"); return this.id+"#"+this.pn+","+this.pe;} public String getTestString () {decimalFormat df = new DecimalFormat getResultString () {decimalFormat df = new DecimalFormat ("0,000000"); return this.id+"#"+df.format (this.pn)+","+df.format (this.pe);}@overdepublic int compareto (enpoint fronge) {id (this.id <free. else if (this.id> ore.id) return1; elsereturn0;}}(2) TrauceoryCompressionMain.java
Пакет cc.xidian.main; импорт java.io.*; import java.text.decimalformat; import java.util.*; import java.util.list;/***, созданный Hadoop на 2015/12/19. Exception{//------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- pGPSArrayInit = new 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 = новый файл ("2007-10-14-gps.log"); // Оригинальный файл файла файла данных ogps = новый файл ("2015-12-25-gps-result.log"); // Фильтрованный объект данных // Сохраняйте исходное значение широты и далеты после конвертации в градусах, и в значительном значении, где, и не имеют большого значения, и есть в диапазоне, и есть такова, и такова, и такова. 6-значные цифры после десятичной точки файла finitgppoint = new File ("2007-10-14-GPS-enpoint.log"); // Сохраняйте конвертированный файл данных исходной точки широты и координаты долготы после конвертированного файла ftestinitpoint = new File ("2007-10-14-gps initteStpoint.log"); // feated rigital rigital natude corniate data intatin ftestfilterpoint = new File ("2015-12-25-25-gps-filtertestpoint.log"); // Используется для фильтрованной файла данных о точке координат и долготы координат после после simulation//------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- PGPSArrayInit); // Написать преобразованные исходные данные о широте и точке долготы в файловую систему.out.println (pgpsarrayinit.size ()); // Вывод количества исходной широты и точки долготы и долготы coordinates//---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 30.0; // Установить максимальный порог ошибки расстояния pgpsarrayfilter.add (pgpsarrayinit.get (0)); // Получить координаты первой оригинальной широты и долготы и добавьте их в фильтрованную массив Pgpsarrayfilter.add (pgpsarrayinit.get (pgpsarrayinit.s (1); 1); Широта и точка долготы и добавить их в отфильтрованную матрицу Enpoint [] enpinit = new Enpoint [pgpsarrayinit.size ()]; // Использование точечного массива для получения всех координат точек для последующего итератора сжатия <enpoint> iinit = pgpsarrayinit.iterator (); jj = 0; while (iinit.hasnext ()) {enpinit [jj] = iinit.next (); jj ++;} // Скопируйте координаты точки в ArrayList в массив точек int int int = 0; // START SPORCFICT int end = pgpSarrayInit.size ()-1; // end sepcript sepcript. TrajCompressc (Enpinit, PgpsArrayfilter, Start, End, Dmax); // DP System System.out.println (pgpsarrayfilter.size ()); // points//---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Enpoint [pgpsarrayfilter.size ()]; // Использование массива точек для получения фильтрованных координат точек, для следующего итератора сортировки <enpoint> if = pgpsarrayfilter.iterator (); int i = 0; while (if.hasnext ()) {enpfilter [i] = if.next (); в точечные массивы Arrays.sort (enpfilter); // sort for (int j = 0; j <enpfilter.length; j ++) {pgpsarrayfiltersort.add (enpfilter [j]); // Написать координаты сортированных точек в новый комплекс множество}//------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- PGPSArrayFilterSort); // Написать отфильтрованные точки данных о широте и долготе в файл моделирования, формат - «долгота, измерение» // ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- getmeandisterror (pgpsarrayinit, pgpsarrayfiltersort); // Найти среднюю ошибку System.out.println(mDError);//----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- (Double) pgpsarrayfilter.size ()/pgpsarrayinit.size ()*100; // Найти скорость сжатия System.out.println(cRate);//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- и коэффициент сжатия writeFilterPointToFile(oGPS,pGPSArrayFilterSort,mDError,cRate);//----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------. @param fgps: файл исходных данных* @return pgpsarrayinit: return arraylist массив, который сохраняет все координаты точек* @Throws Exception*/public Static ArrayList <Enpoint> getEnpointfromfile (file fgps) throws exection {arraylist <enpoint> pgpsarray = new ArrayList <Enpoint> (); if (fgps.exists () && fgps.isfile ()) {inputStreamReader Read = new InputStreamReader (New FileInputStream (FGPS)); BufferedReader Hearer = new BufferedReader (read); String Str; strgps; int i = 0; str.split ("); enpoint p = new enpoint (); p.id = i; i ++; p.pe = (dftodu (strgps [3])); p.pn = (dftodu (strgps [5])); pgpsArray.add (p);} funter.clase () return pcpsarray; average 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) Throws Exception {iterator <enpoint> 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 (crate)+"%"+"#"/n "; byte [] bmc = strmc.getBytes();rFilter.write(bmc);rFilter.close();}/*** Function function: Save the converted original latitude and longitude data points into a file* @param outGPSFile* @param pGPSPointFilter* @throws Exception*/public static void writeInitPointToFile(File outGPSFile,ArrayList<ENPoint> pgpspointfilter) throws exception {iterator <enpoint> ifilter = pgpspointfilter.iterator (); randomaccessfile rfilter = new randomaccessfile (outgpsfile, "rw"); while (ifilter.hasnext ()) {enpoint p = ifilter.next (); p.tostring ()+"/n"; byte [] bfilter = sfilter.getbytes (); rfilter.write (bfilter);} rfilter.close ();}/*** Функция функции: записать широту и координат Donitude Poit Array* @throhs Exception*/public static void writetestpointtofile (file OutgpsFile, ArrayList <Enpoint> pgpspointfilter). Вызывает исключение {iterator <enpoint> ifilter = pgpspointfilter.iterator (); randomaccessfile rfilter = new randomaccessfile (outgplator (); randaccessfile rfilter = new randomaccessfile (outgplator (); "randaccessfile rfilter = new randomaccessfile. while (ifilter.hasnext ()) {enpoint p = ifilter.next (); string sfilter = p.getTestString ()+"/n"; byte [] bfilter = sfilter.getbytes (); rfilter.write (bfilter);} rfilter.clase ();}/*** функция rawnitue function and rawnitude and rawnitue function: ***. градусы* @param str: исходные координаты широты и долготы* @return: вернуть данные степени для соответствующего*/public static double dftodu (string str) {int indexd = str.indexof ('.'. '); String strm = str.substring (0, indexd-2); String strn = str.substring (indexd-2); double.parsedouble (strm)+double.parsedouble (strn)/60; return d;}/*** Функция: хранить шесть десятичных знаков двойного номера* @param d: исходное двойное число* @return возвращать конвертированное двойное число*/public static doublepointsix (double d) {decimalformat df = new Decimalformat ("0,000000"); Double.parsedouble (df.format (d));}/*** Функция: Рассчитайте расстояние между точкой PX и прямой линией, определяемой точкой PA и PB, используя равный метод, используя область треугольника (найдите с помощью формулы Helen). расположен*/public static double disttosegment (enpoint pa, enpoint pb, enpoint px) {double a = math.abs (Geodist (pa, pb)); Double b = math.abs (Geodist (pa, px)); Double c = Math.abs (Geodist (pb, px)); Double p = (a+b+c) /2.0; 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 latitude and longitude points that are 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 (delta_lon); double top_2 = math.cos (radlat1) Math.sin (Radlat1) * math.cos (Radlat2) * math.cos (delta_lon); двойной верх = мат. Math.cos (delta_lon); double delta_sigma = math.atan2 (вверху, внизу); двойное расстояние = delta_sigma* 6378137.0; return Distance;}/*** Функция функции: angle Radian* @param d: angel* @return возвращаемый Radian*/public static double Rad (Double d) {return d* math.pi/180. Максимальный предел расстояния, исходная траектория рекурсивно отображается с использованием метода DP для получения сжатой траектории* @param enpinit: оригинальная широта и точки координат долготы Trajcompressc (enpoint [] enpinit, arraylist <enpoint> enparrayfilter, int start, int end, double dmax) {if (start <end) {// Рекурсивное условие двойное maxdist = 0; // максимальное расстояние int cur_pt = 0; // текущий подход для (int i = 1; i <end; Disttosegment (enpinit [start], enpinit [end], enpinit [i]); // Расстояние от текущей точки до соответствующего сегмента линии if (curdist> maxdist) {maxdist = curdist; cur_pt = i;} // Нахождение подписчика максимального расстояния максимальное расстояние максимальное расстояние максимальное расстояние} // //, если ток, максимальный расстояние, максимум, максимальное расстояние, максимальное расстояние. if (maxdist> = dmax) {enparrayfilter.add (enpinit [cur_pt]); // Добавить текущую точку в фильтрованную массив // Разменить исходный сегмент линии в два сегмента, сосредоточенные на текущей точке и выполните рекурсивную обработку соответственно DAMPRESPREC TrajCompressc (enpinit, enparrayfilter, cur_pt, end, dmax);}}}/*** Функция функции: Найдите среднюю ошибку расстояния* @param pgpsarrayinit: исходные координаты точек данных* @param pgpsarrayfiltersort: Filmed Data Cordinates* @retun pgpsarrayinit, arraylist <enpoint> pgpsarrayfiltersort) {double sumdist = 0,0; для (int i = 1; i <pgpsarrayfiltersort.size (); i ++) {int start = pgpsarrayfiltersort.get (i-1) .id; int end = pgpsarrayfilters.get (i). j = start+1; j <end; j ++) {sumdist+= disttosegment (pgpsarrayinit.get (start), pgpsarrayinit.get (end), pgpsarrayinit.get (j));}} double madist = sumdist/(pgpsarrayinit.size ();Результаты процедуры части IV
4.1 Результаты вывода программы
Сжатые результаты:
(1) общее количество баллов: 140 баллов; (2) Средняя ошибка расстояния: 7,943786; (3) Скорость сжатия: 4,4444%
4.2 Результаты моделирования
После сжатия траектории мы преобразуем исходные точки координат широты и долготы в сжатые и отфильтрованные точки широты и координат долготы. Мы пишем эти две точки координируют данные в два файла, а затем рисоваем траектории до и после сжатия в соответствии с этими двумя файлами, и сравниваем их. Основываясь на результатах сравнения, мы можем увидеть, эффективен ли наш алгоритм сжатия траектории. Окончательный результат сравнения показан на рисунке 4.1:
Резюме части 5
В процессе написания этой программы я столкнулся с различными проблемами и узнал много опыта программирования. Ниже приводится краткое изложение проблем и решений, и, наконец, выдвинуло предложения по улучшению недостатков программы.
5.1. Проблемы и решения встречаются
Вопрос 1: Проблема заказа по порядку широты и долготы
Решение: параметры в формуле расстояния заключается в том, что широта находится впереди, а долгота находится сзади, а порядок точек широты и координат долготы необходимо скорректировать.
Вопрос 2: Расстояние не может быть отрицательным
Решение: Убедитесь, что обнаруженное расстояние не может быть отрицательным, добавьте функцию абсолютного значения.
Вопрос 3: Детали реализации алгоритма DP
Решение: я начал использовать ArrayList Array для решения проблемы индекса. Была огромная ошибка при рекурсии. Позже я переключился на использование обычных подписок массива для рекурсии, и результат был намного лучше.
5.2 Существующие недостатки и перспективы
(1) При выполнении сжатия траектории алгоритм DP является самым простым алгоритмом и не самый лучший. Некоторые алгоритмы с хорошими результатами могут быть использованы для снова выполнения сжатия траектории;
(2) Записи данных этого эксперимента составляют 3150, а объем данных не является большим. Что мне делать, если есть 1 миллиард данных? Мы можем рассмотреть аппаратные, распределенные, предварительные обработки данных, сегментацию данных и хранилища данных с хорошей производительностью.
Выше приведено полное содержание этой статьи о подробном кодексе алгоритма Дугласа-Пайкера для программирования Java для реализации сжатия траектории. Я надеюсь, что это будет полезно для всех. Если есть какие -либо недостатки, пожалуйста, оставьте сообщение, чтобы указать это. Спасибо, друзья, за вашу поддержку на этом сайте!