Усовершенствованный способ построения геопространственного индекса, использующего ZIPU-кривые

Одним из распространенных применений кривых, заметающих пространство, является построение геопространственных индексов. Геопространственные индексы используются для обеспечения поиска, хранения и обработки данных ДЗЗ. В существующих индексах широко используются кривые, заметающие пространство (Z-кривая, кривая Гильберта, H-кривая и т. д.). К сожалению, при использовании данных кривых не учитываются географические (данные о континентах и островах), политические (данные о границах стран и регионов) и другие факторы.

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

ZIPU-кривые – класс кривых, заметающих пространство, использующий шаблоны Z, И, П, U. Основой эффективного использования ZIPU-кривых является подготовка шаблонов декомпозиции с помощью построения базовых линий.

Базовые линии задают обход соседних ячеек в произвольном порядке.
Шаблоны декомпозиции ZIPU-кривых определяют способ иерархического разбиения ячейки с использованием шаблонов Z, И, П, U.

Алгоритм подготовки шаблона в общем виде:
1. Разделение области определения на прямоугольные ячейки;
2. Группировка ячеек в блоки;
3. Для каждого блока создается множество базовых линии обхода ячеек внутри блока для разных уровней детализации;
4. Построение основной базовой линии обхода блоков на всей области определения;
5. Для каждого блока осуществляется выбор оптимального варианта обхода ячеек на основании нескольких критериев - происходит формирование единой заметающей кривой.

Усовершенствование касается некоторых этапов алгоритма, а именно:
- создание базовых линий (шаги 3 и 4);
- построение основной базовой линии обхода блоков ячеек (шаг 4).

На этапах создания и подбора множества элементов базовой линии оказалось целесообразно проверять возможность декомпозиции данной линии.
Данная проверка может быть выполнена с помощью построения упрощенного ориентированного графа и выполнения поиска пути между начальной и конечной точками.
Сформированы последовательности обхода длиной от 3 до 7 для которых не может быть выполнена декомпозиция, а также предложен универсальный способ проверки с помощью регулярных выражений.
Сформированы базы данных содержащие базовые линии с размерами от 3 до 16 для заметаемых областей различной конфигурации.

Сформулирован алгоритм автоматизированного построения основной базовой линии:
В случае, если количество блоков до 256:
1. Выбрать уровень декомпозиции области определения на блоки;
2. Отметить первый блок обхода;
3. Выбрать несколько следующих блоков (до 16) в зависимости от конфигурации получившейся области;
4. Отметить в этой области начальную и конечную точки;
5. С помощью множества заранее сформированных базовых линий можно выбрать локально оптимальный способ обхода данной области в соответствии с критериями;
6. Если остались необойденные блоки, следует перейти к третьему шагу указанного алгоритма.

Рассмотрено применение расширения данного алгоритма для 1024 ячеек при построении основной базовой линии.