Эффективные алгоритмы геометрического поиска элементов векторных карт

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

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

Наша модель для хранения, поиска и отображения объектов состоит из двух частей:

1. Бинарный файл, содержащий в себе иерархическое разбиение всей области (карты) с помощью оптимизированного 2с1-дерева [6].

2. База данных SQLite [7], содержащая координаты вершин вектор­ных объектов, а так же дополнительные атрибуты, такие как тип объек­та, порог видимости объекта, цвет объекта.

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

Выбор базы данных SQLite обусловлен хорошими временными ха­рактеристиками скорости обработки запросов.

Перемещение по карте и подкачка данных

Для быстрого отображения данных мы будем хранить части области карты вокруг области отображения на трех уровнях детализации (уро­вень «ниже», «текущий» уровень, уровень «выше»). Каждый уровень представляет собой 9 областей части карты при текущем масштабе. Это значит, что, если мы хотим отобразить на экран область карты размером AxB, то на «текущем» уровне будут храниться 9 областей размером AxB (одна центральная и 8 обрамляющих), на уровне «выше» будут хранить­ся 9 областей размером A1xB1, где A1 и B1 в два раза больше, чем A и B соответственно (т.е. имеем масштаб в два раза меньше) и на уровне «ниже» будут храниться 9 областей размером A2xB2, где A2 и B2 в два раза меньше, чем A и B соответственно (т.е. имеем масштаб в два раза больше). Каждая из 9 областей любого из трех уровней детализации бу­дет представлена в памяти битовым изображением фиксированного раз­мера (размер битового изображения для всех областей одинаковый) (рис.1). Это позволяет нам не хранить в памяти все векторные объекты, попадающие в некоторую область, а хранить только битовые изображе­ния, на которых данные объекты были отрисованы с соответствующим масштабом.

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

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

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

Движение между уровнями может происходить в двух направлениях:

  1. На уровень «выше» — с увеличением размера отображаемой части карты.
  2. На уровень «ниже» — с уменьшением размера отображаемой части карты.

Для реализации плавного и быстрого движения между уровнями мы перед переходом на уровень «ниже» «растягиваем» часть карты «теку­щего» уровня с текущей детализацией. А при переходе на уровень «вы­ше» мы «сжимаем» часть карты «текущего» уровня. Целесообразно ис­пользовать несколько таких промежуточных уровней «сжатия» («растя­жения»), это позволит выиграть время на загрузку нового уровня.

При переходе через последний уровень сжатия (растяжения) мы ме­няем «текущий» уровень на уровень «выше» («ниже»), используем «рас­тяжение» («сжатие») на нем и производим подгрузку нового уровня.

Преимущества метода

При работе с картографическими системами важное место отводится скорости поиска объектов и объему оперативной памяти, требуемой для работы приложения.

Главным преимуществом данного подхода является время поиска объектов, попадающих в целевую область. При использовании триви­ального последовательного поиска среди N объектов время запроса со­ставляет O(N). При использовании оптимизированного 2-d дерева время запроса в среднем составляет O (log N + k), где k — число объектов, по­павших в область. В современных картографических системах исполь­зуются такие иерархические структуры данных как квадродеревья, мат­ричные квадродеревья и оптимизированные квадродеревья [8]. Не смот­ря на то, что эти структуры данных имеют в среднем такую же асимпто­тику времени запроса как и оптимизированное 2-d дерево, на практике они в 2-5 раз уступают по скорости оптимизированному 2-d дереву.

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

Заключение

Использование реорганизации исходного пространства данных с по­мощью оптимизированного 2-d дерева, а так же использование динами­ческой многоуровневой подкачки данных с разной степенью детализа­ции позволяет работать с векторными картами очень больших размеров и перемещаться по ним с достаточно хорошей скоростью без видимых задержек.

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Этот сайт использует Akismet для борьбы со спамом. Узнайте как обрабатываются ваши данные комментариев.