УДК 51-74

ФОРМИРОВАНИЕ ОПТИМАЛЬНОГО НАБОРА ТОЧЕК АППРОКСИМАЦИИ ВЕТВЕЙ ГРАФА ДОРОЖНОЙ СЕТИ ИЗ ОБЩЕЙ БАЗЫ ДАННЫХ ДОРОЖНОЙ СЕТИ

Беляков Алексей Константинович1, Горелкин Георгий Александрович1
1Национальный исследовательский ядерный университет (МИФИ)

Аннотация
Рассматривается метод формирования оптимальной упорядоченной выборки М точек из общего набора интерполяционных точек кривой, обеспечивающие минимум интеграла квадрата ошибки интерполяции. Для решения задачи предлагается критерий, представ-ленный в виде суммы частных интегральных критериев. Данный подход позволяет использовать для решения общей оптимизационной задачи принцип дискретного динамического программирования Беллмана. Предлагаемый метод разрабатывается для использования в геоинформационных системах при формировании баз данных, содержащих интерполяционные точки линий (дорожная сеть, различные границы и прочие линейные объекты) для последующего их отображения на карте местности. А также для предвари-тельной фильтрации данных, вызванной ограничениями оперативной памяти при использовании в специализированных навигационных устройствах.

Ключевые слова: геоинформационная система, граф решения, динамическое программирование, интерполяция, критерий оптимизации, линейный объект, узловые точки


ROAD MAP TRACK POINTS OPTIMAL RENDERING FROM OPEN DATABASES

Beliakov Alexey Konstantinovich1, Gorelkin Georgiy Aleksandrovich1
1National Research Nuclear University MEPhI (Moscow Engineering Physics Institute)

Abstract
In article we suggests method of forming the optimal ordered set of points from the set of interpolation points described an arbitrary curved line. Our method providing a minimum integral square error of interpolation. To solve the problem we suggest a criterion presented in the form of a sum of partial integral criteria. This approach allows use Bellman’s general principle of the discrete dynamic programming to solve the optimization problem. The proposed method are being developed for use in geographic information systems at formation of databases containing lines presented as set of interpolation points (roads, borders and various other linear objects) for subsequent displaying on a map of the area. Also for the preliminary filtering of data for use in specialized navigation devices, caused by the limitations of memory of such devices.

Keywords: : dynamic programing, geographic information systems, graph of solutions, interpolation, line node points, optimization criteria


Рубрика: 01.00.00 ФИЗИКО-МАТЕМАТИЧЕСКИЕ НАУКИ

Библиографическая ссылка на статью:
Беляков А.К., Горелкин Г.А. Формирование оптимального набора точек аппроксимации ветвей графа дорожной сети из общей базы данных дорожной сети // Современные научные исследования и инновации. 2015. № 7 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2015/07/53963 (дата обращения: 20.11.2016).

В настоящее время в различных областях народнохозяйственной деятельности нашли широкое применение геоинформационные системы различного назначения. Как правило, в геоинформационных системах границы областей и фронтов распространения различных физических процессов, линии уровня рельефа местности, траектории движения подвижных объектов, сеть автодорог и т.д. отображаются на карте  с помощью сплайн-интерполяции выбранного порядка по упорядоченному множеству большого числа точек визуализации. Например, сеть автомобильных дорог строится на основе обработки информации, получаемой от спутниковой навигационной системы ГЛОНАСС с интервалом в 1секунду. Эта информация [1] преобразуется в геоцентрические координаты текущей точки дорожной сети и сохраняется в базе данных дорожной сети. Очевидно, такое подробное представление существенно затягивает и усложняет процесс последующей обработки данных дорожной сети в целях дальнейшего использования. Причем, многое из этой информации является избыточным и может быть выведено из базы данных без существенной потери точности описания дорожной сети. Таким образом, возникает задача максимального сохранения степени кривизны исходного линейного объекта при заданном уровне фильтрации.

В этой связи актуальной становится задача выбора упорядоченного набора M точек визуализации из первоначального упорядоченного набора N точек визуализации.

Критерий выбора упорядоченных точек визуализации

В качестве критерия выбора точек рационально выбрать условие минимизации площади находящейся между линией, построенной по M упорядоченным точкам (линия Lm ), и линии, построенной по N, упорядоченным точкам (линия Ln). Такой критерий эквивалентен интегралу квадрата отклонения точек линии Lm от соответствующих точек линии Ln.

Пример формирования линии. Для примера: N=11, M=6.

Пример формирования линии. Для примера: N=11, M=6.

Так как узловые точки совпадают, то общая площадь между линиями может быть представлена в виде суммы площадей, заключенных между узловыми точками. При этом критерий оптимизации выбора точек из множества  записывается в виде суммы.

Так как общее число точек множества  равно, то нетрудно заключить, что если первые  M-1 точек последовательностей совпадают, то интервал между последними точками будет содержать N-M  точек множества  и наоборот. Кроме того, общее число точек – N.

Решение задачи минимизации критерия методом дискретного динамического программирования

Представление критерия в виде суммы дает основание использовать принцип метода дискретного динамического программирования [2]. Решение данной оптимизационной задачи удобно представить в виде ограниченного графа на сетке решений. Для примера: красной пунктирной линией отмечены «условно» оптимальные пути, красной линией отмечен оптимальный путь. (рис. 2) [3,4].

Пример графа решения задачи методом дискретного динамического программирования

Пример графа решения задачи методом дискретного динамического программирования

По горизонтальной оси откладываются уровни решения задачи, причем число уровней соответствует числу точек множества . По вертикальной оси – точки множества , в которые можно попасть на i-том уровне. Очевидно, в силу ограничений каждый уровень (кроме первого и последнего) содержит N-M+1 точек.

При формировании третьего уровня, в каждую точку  уровня 3 возможно попасть многими путями из точек 2-го уровня (рис. 2). При этом каждому пути  будет соответствовать свое значение суммы площадей. Очевидно, чем больше номер уровня, тем больше путей могут привести в эту точку, и тем больше различных значений площадей будет соответствовать этой точке. Выберем путь в точку , который соответствует минимальной площади. С этой целью для каждой точки ищется такой путь, который обеспечивает минимум критерия. На рисунке 2 в качестве примера оптимальные пути для точек уровня 3 выделены красным цветом. Описанная выше процедура формирования точек уровня 3 повторяется для следующих уровней. Последний уровень имеет только одну точку , попасть в которую можно из точек предыдущего уровня. Причем, каждому пути будет соответствовать свое значение площади. Теперь возможно найти единственный путь, обеспечивающий минимум критерия и пройти его по оптимальным точкам в обратном направлении.

Перечисленная последовательность и будет оптимальным набором точек множества, обеспечивающих минимум критерия. Зная номера точек множества нетрудно найти оптимальное число точек между узлами , которые в дальнейшем не будут участвовать в процессе описания дорожной сети. Для оценки эффективности предложенного алгоритма проводится оптимизация набора точек визуализации. Особенностью приведенного выше метода является максимальное сохранение степени кривизны исходного линейного объекта при заданных коэффициентах фильтрации.

Пример использования  принципов оптимальной фильтрации точек дорожной сети

Работоспособность предложенного алгоритма была исследована на базе упорядоченной последовательности точек, представленных в OSM [7] в формате WGS84 в виде широты/долготы (WGS84— трёхмерная система координат для позиционирования на Земле, в которой за основу взят эллипсоид с большим радиусом — 6 378 137 м (экваториальный) и меньшим — 6 356 752,3142 м (полярный)). Так как в качестве критерия выбора точек было поставлено условие минимизации площади между линией, построенной по M упорядоченным точкам, и линии, построенной по N упорядоченным точкам (N>M), то возникла необходимость подсчета площадей произвольных многоугольников, лежащих на эллипсоиде и задаваемых точками, геоцентрические координаты которых известны.Для решения этой задачи координаты точек пути переводятся в координаты Меркатора[6].

Как уже отмечалось выше, в качестве критерия выбора точек было поставлено условие минимизации площади между линией, построенной по M упорядоченным точкам визуализации, и линии, построенной по N упорядоченным точкам визуализации (N>M). Таким образом, задача нахождения критерия сводится к задаче нахождения площади произвольного многоугольника, заданного координатами вершин. Для подсчета площади берется произвольная точка О (например, начало координат) и вычисляется площадь многоугольника (рис.3) при обходе вершин в последовательности 1,2,…,N [4].

подсчет площади многоугольника (не самопересекающийся многоугольник)

подсчет площади многоугольника (не самопересекающийся многоугольник)

Для случая самопересекающегося многоугольника для каждой пары отрезков решается задача о пересечении двух прямых. Если точка пересечения существует, то определяется, принадлежит ли она отрезкам, образующим многоугольник. Далее самопересекающийся многоугольник делится в точке пересечения на не самопересекающиеся многоугольники, площадь которых находится изложенным выше методом.

Построенная по полученному оптимальному набору точек кривая представлена на рисунке 4. Ошибка фильтрации точек относительно первоначальной кривой при уровне фильтрации 2  составляет Sф=1,1у.е

Желаемый набор из M=7 точек визуализации

Желаемый набор из M=7 точек визуализации

Для оценки работоспособности разработанного математического и программного обеспечения был проведен тестовый расчет при N=54 при коэффициентах фильтрации 2, 3 и 5. Результаты тестового расчета показали, что кривизна исходного объекта сохраняется даже при уменьшении числа точек с 54 до 10.

Заключение

Как уже отмечалось, приведенный алгоритм может быть применен в информационных системах различного назначения для фильтрации большого объема данных при обработке линейных объектов, в частности, маршрутов (треков), полученных с помощью автоматизированных средств записи перемещения объектов (GPS/ГЛОНАСС-приёмники), для уменьшения времени изображений различных линейных объектов в ГИС.

Кроме того, многие специализированные навигационные устройства позволяют загружать в память пути (треки) с ограниченным количеством точек (например, максимальное количество точек пути, которые можно загрузить в популярные устройства серии FORERUNNER производства компании GARMIN составляет 500 точек) Приведенный метод позволяет осуществлять предварительную обработку данных для загрузки в такие устройства.


Библиографический список
  1. Бабич О.А. Обработка информации в навигационных комплексах.-М.: Машиностроение, 1991, -512с.
  2. Крицына Н.А. Оптимизация параметров численного решения уравнений динамики. Сборник научных трудов «Алгоритмы цифрового оценивания, контроля и управления» под ред. Д.т.н,, профессора Иващенко Н.Н. – М: АТОИЗДАТ, 1990, – 180 с.
  3. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. — М.: Наука, 1978.
  4. И. Х. Сигал, А. П. Иванова Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учеб. пособие. — Изд. 2-е, испр. — М.: ФИЗМАТЛИТ, 2003. — 240 с.
  5. Клейн.Ф. Элементарная математика с точки зрения высшей: В 2-х томах. Т.2.Геометрия: Пер. с нем. под ред. В.Г.Болтянского. – Изд. 2-е. – М.:Наука. Гл. ред. физ. мат. лит.,1987. – 416с.
  6. http://wiki.gis-lab.info/  Пересчет координат из Lat/Lon в проекцию Меркатора и обратно.
  7. http://habrahabr.ru/ Структура данных проекта OpenStreetMap.


Все статьи автора «Алексей Константинович»


© Если вы обнаружили нарушение авторских или смежных прав, пожалуйста, незамедлительно сообщите нам об этом по электронной почте или через форму обратной связи.

Связь с автором (комментарии/рецензии к статье)

Оставить комментарий

Вы должны авторизоваться, чтобы оставить комментарий.

Если Вы еще не зарегистрированы на сайте, то Вам необходимо зарегистрироваться:
  • Регистрация