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

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

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

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

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

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

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

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

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

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

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

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

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

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

Работоспособность предложенного алгоритма была исследована на базе упорядоченной последовательности точек, представленных в 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 точек визуализации

Для оценки работоспособности разработанного математического и программного обеспечения был проведен тестовый расчет при 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.

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