В настоящее время геоинформационные системы нашли широкое применение в различных областях деятельности. Как правило, в геоинформационных системах границы областей и фронтов распространения различных физических процессов, линии уровня рельефа местности, траектории движения подвижных объектов и т.д. отображаются на карте с помощью сплайн-интерполяции выбранного порядка по упорядоченному множеству 
, состоящему из N точек (N - большое число). Причем многие из этих точек являются избыточными и могут быть выведены из базы данных без существенной потери точности интерполяции.
В этой связи актуальной становится задача определения упорядоченного набора M точек из первоначального множества точек , (
). В качестве критерия выбора точек рационально поставить условие минимизации площади, находящейся между линией, построенной по M упорядоченным точкам (линия 
), и линии, построенной по N упорядоченным точкам (линия 
). Такой критерий эквивалентен интегралу квадрата отклонения точек линии от соответствующих точек линии (рис. 1).
Рис. 1. Пример формирования линии .
Для примера: N=11, M=6.
Пусть 
, – число точек множества между точками множества 
, тогда справедливы следующие соотношения:
1. 
- первые и последние точки множеств 
и 
совпадают;
2. 
- узловые точки линий и совпадают.
Так как узловые точки совпадают, то общая площадь между линиями может быть представлена в виде суммы площадей, заключенных между узловыми точками. При этом критерий оптимизации выбора точек из множества запишем в виде суммы
(1)
где 
- площадь фигуры, находящейся между узловыми точками. 
.
Так как общее число точек множества 
равно 
, то нетрудно заключить, что если первые 
точек последовательностей совпадают, то интервал между последними точками 
и 
будет содержать 
точек множества 
, и, наоборот, если последние точек последовательностей совпадают, то интервал между первыми точками 
и 
будет содержать точек множества . Кроме того, общее число точек – N. Таким образом, ограничения, накладываемые на аргумент оптимизации, будут иметь вид:
, 
- целое число. (2)
. (3)
Представление критерия (1) в виде суммы дает основание использовать принцип метода дискретного динамического программирования [3; 4].
Решение данной оптимизационной задачи удобно представить в виде ограниченного графа на сетке решений (рис. 2) [2; 5].
Рис. 2. Граф решения задачи методом дискретного динамического программирования.
Для примера: 
Красной пунктирной линией отмечены «условно» оптимальные пути,
красной линией отмечен оптимальный путь.
По горизонтальной оси будем откладывать уровни решения задачи, причем число уровней соответствует числу точек множества 
; по вертикальной оси – точки множества , в которые можно попасть на i-м уровне. Очевидно, в силу ограничений (2) и (3), каждый уровень (кроме первого и последнего) содержит 
точек.
Так как на первом уровне имеется единственная точка 
, то в точку 
второго уровня возможно попасть только единственным путем 
(рис. 2). При этом каждой точке уровня 2 будет соответствовать площадь фигуры 
, опирающейся на хорду между точками и 
(рис. 1). Значения этих площадей запоминаем.
При формировании третьего уровня в каждую точку 
уровня 3 возможно попасть многими путями из точек 2-го уровня (рис. 2). При этом каждому пути 
будет соответствовать свое значение суммы площадей
. (4)
(5)
Очевидно, чем больше номер , тем больше путей могут привести в эту точку, и тем больше различных значений площадей будет соответствовать этой точке. Выберем путь в точку 
, который соответствует минимальной площади. С этой целью для каждой точки найдем такое 
, которое обеспечивает минимум критерия (4),
, 
(6)
(7)
Полученные значения 
, 
запоминаем. На рисунке в качестве примера оптимальные пути для точек уровня 3 выделены красным цветом.
Описанную выше процедуру формирования точек уровня 3 повторяем для уровней 
В результате для уровня 
будем иметь следующие соотношения:
, 
(9)
(10)
Полученные значения 
, 
запоминаем.
Последний уровень M имеет только одну точку 
, попасть в которую можно из точек предыдущего уровня 
(рис. 2). Причем каждому пути 
будет соответствовать значение площади:
(11)
Найдем единственный путь, обеспечивающий минимум критерия (11):
, (12)
(13)
Используя соотношения (12), (9) и (6), пройдем весь путь по оптимальным точкам в обратном направлении:
(14)
Перечисленная в (14) последовательность будет оптимальным набором точек множества 
, обеспечивающих минимум критерия (1).
Зная номера точек множества 
, входящих в множество , нетрудно найти оптимальное число точек между узлами 
.
Приведенный алгоритм может быть применен в информационных системах различного назначения для «фильтрации» большого объема данных при обработке линейных объектов. В частности, маршрутов (треков), полученных с помощью автоматизированных средств записи перемещения объектов (GPS/ГЛОНАСС-приемники), для уменьшения времени обработки изображений различных линейных объектов в ГИС.
Кроме того, многие специализированные навигационные устройства позволяют загружать в память пути (треки) с ограниченным количеством точек (например, максимальное количество точек пути, которые можно загрузить в популярные устройства серии FORERUNNER производства компании GARMIN составляет 500 точек). Приведенный метод позволяет осуществлять предварительную обработку данных для загрузки в такие устройства [1]. Особенностью метода является максимальное сохранение степени кривизны исходного линейного объекта при заданном уровне фильтрации.
Рецензенты:
Загребаев Андрей Маркоянович, д.т.н., профессор, Национальный исследовательский ядерный университет (МИФИ), г. Москва.
Крянев Александр Витальевич, д.ф-м.н., профессор, Национальный исследовательский ядерный университет (МИФИ), г. Москва.