Сжатие векторных данных

Рассматривая растровые модели данных, мы обнаружили, что данные могут быть упакованы разными способами для сокращения объема занимаемой памяти. Хотя векторные модели более эффективны при хранении больших объемов пространственных данных, нам все же нужно рассмотреть компрессию. Метод сжатия, который мы сейчас рассмотрим, на самом деле довольно похож на простой процесс кодирование; разработанный более века назад сэром Фрэнсисом Гальтоном [Francis Galton, 1884]. Будет полезно переместиться во времени и присоединиться к английскому ученому, когда он пытался создать рукописную схему записи направлений во время географических экскурсий. Форма, придуманная им, — сама простота. Он просто использовал восемь чисел для обозначения четырех главных и четырех промежуточных географических направлений (Рисунок 4.1ба).

Удивительно похожая модель кодирования, разработанная в наше время, известнакак цепочечные коды Фримэна-Хофмэна [Freeman, 1974] (Рисунок 4.16b). Целые числа от 0 до 7 назначаются восьми векторам направлений. Метод Фримэна-Хофмэна использует те же главные и промежуточные направления для векторов, что и Гальтон в своих путешествиях для наземной навигации. Назначая длину для каждого вектора, мы можем записывать отдельные линейные объекты, указывая их начало, длину, направление, в котором они рисуются и где они меняют направление. Существуют многие вариации на эту тему, включая увеличение количества кодов до 16-ти (Рисунок 4.16с) или даже до 32-х для увеличения точности. Результат один - сокращение объема векторной БД.

Рисунок 4.16. Цепочечные коды. Сравнение компактных моделей для указания направлений: разработанной сэром Фрэнсисом Гальтоном и усовершенствованной в виде цепочечных кодов Фримэна-Хофмэна. Обратите внимание на сильное сходство между старой и новой моделями.

Хотя модели цепочечных кодов существенно экономят память, они, как и спагетти-модель, не содержат явной топологической информации. Это ограничивает их полезность для функций хранения, выборки и вывода из-за аналитических ограничений нетопологических структур данных. Кроме того, тот способ, которым кодируются линии и области в виде векторов, при выполнении преобразований координат, особенно поворотов, вызывает значительные накладные вычислительные расходы. Модели цепочечных кодов хороши для определения расстояний и форм, поскольку большая часть этой информации имеется в самих направляющих векторах. И поскольку этот подход очень похож на то, как работают векторные плоттеры (см. Главу 14), эти модели эффективны для выполнения быстрого вывода на плоттер.