автореферат диссертации по инженерной геометрии и компьютерной графике, 05.01.01, диссертация на тему:Алгоритмы оперативного отображения большеформатных цифровых карт

На правах рукописи

'.Л

4848517

е/ -=

Матвеев Захар Александрович

АЛГОРИТМЫ ОПЕРАТИВНОГО ОТОБРАЖЕНИЯ БОЛЬШЕФОРМАТНЫХ ЦИФРОВЫХ КАРТ

05.01.01 - Инженерная геометрия и компьютерная графика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

2 а ЮН 2011

Нижний Новгород - 2011

4848517

РАБОТА ВЫПОЛНЕНА В ГОУ ВПО НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. Н.И. ЛОБАЧЕВСКОГО-

Научный руководитель доктор технических наук, профессор Кетков Юлий Лазаревич

Официальные оппоненты: доктор технических наук, профессор Косяков Сергей Витальевич, кандидат технических наук, доцент Жерздев Сергей Владимирович

Ведущая организация

ГОУ ВПО«Ижевский государственный технический университет»

Защита состоится "21" июня 2011 г. в 15 часов на заседании диссертационного совета ДМ 212.162.09 при ГОУ ВПО «Нижегородский государственный архитектурно-строительный университет» по адресу: 603950, г. Нижний Новгород, ул. Ильинская, 65, корпус 5, аудитория 202.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «Нижегородский государственный архитектурно-строительный университет».

Автореферат разослан «18» мая 2011 г.

Ученый секретарь диссертационного совета

кандидат педагогических наук, доцент

Н.Д. Жилина

Общая характеристика работы

Актуальность работы. Современная экономическая, управленческая и исследовательская деятельность человека тесно связана с анализом пространственного положения объектов земной поверхности. Такого рода сведения необходимы при решении широкого спектра задач. Это - управление наземным, воздушным и водным транспортом, проектирование, разработка и эксплуатация различных коммуникаций, гражданское строительство и управление коммунальным хозяйством, землеустройство и экология, разведка полезных ископаемых, оборонная деятельность и многое другое.

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

В настоящее время существует множество автоматических и автоматизированных картографических систем (АКС), использующих различного рода программные и аппаратные средства, ориентированные на работу с геоинформационными данными. Такие комплексы обеспечивают сбор, редактирование, хранение, оперативную визуализацию и распространение пространственной информации в виде электронных карт или их твердых копий. Описание цифровой карты на ту или иную территорию земной поверхности, хранящееся в специализированной базе картографических данных (СБКД), представляет собой совокупность сведений о пространственных объектах двух видов: геометрических (позиционных) и атрибутивных (семантических). Геометрическая часть отражает геометрию объекта (указание положения объекта, элементы графического оформления), а атрибутивная содержит характеристики объектов (их качественные или количественные параметры) и пространственно-логические связи между ними.

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

карты принимается специалистом-редактором по результатам тщательного визуального контроля содержимого СБКД.

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

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

Объектом исследования является технология визуализации векторных графических описаний болыпеформатных листов электронных карт.

Предметом исследования являются алгоритмы и средства повышения производительности систем отображения графических файлов формата НР-ОЬ.

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

Для достижения поставленной цели требуется решение следующих основных научных и практических задач:

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

2. Исследование внутренних форматов и математических моделей местности, используемых для представления графических образов электронных карт.

3. Разработка алгоритмов предварительной обработки исходного графического описания и индексирования групп графических операторов.

4. Разработка алгоритмов масштабирования и плавной локальной навигации между смежными фрагментами цифровых карт.

5. Применение оптимального алгоритма отсечения отрезков в задачах массовой обработки операторов линейного перемещения пишущего узла.

6. Анализ возможностей распараллеливания вычислительного процесса визуализации.

7. Реализация разработанных алгоритмов в виде программной подсистемы визуализации графических файлов формата HP-GL.

8. Экспериментальное сравнение производительности разработанной подсистемы с зарубежными аналогами.

Методы исследования. Теоретические исследования выполнены с использованием методов дискретной математики (теории графов, математической логики), вычислительной геометрии, компьютерной графики.

Экспериментальные исследования выполнены с помощью разработанной подсистемы визуализации, ряда отечественных АКС и известных визуализато-ров SPLOT32 и View Companion (Premium) for Windows.

Достоверность и обоснованность полученных в работе результатов и выводов подтверждаются положительными результатами проведенных экспериментальных исследований и опытной апробации подсистемы визуализации на ряде картографических документов, подготовленных в научно-исследовательском институте прикладной математики и кибернетики Нижегородского государственного университета им. Н.И. Лобачевского (НИИ ПМК).

Научная новизна состоит в том, что:

• предложены алгоритмы предварительной обработки графического файла в формате HP-GL, обеспечивающие автоматическое создание иерархической кластерной модели исходного файла;

• разработан внутренний формат представления графических данных и серия алгоритмов его индексирования;

• предложен алгоритм плавной локальной навигации по смежным кадрам изображения, обеспечивающий повышение производительности процесса визуализации на 30%;

На защиту выносятся:

1. Алгоритмы предварительной обработки исходного изображения.

2. Внутренний формат графических данных и алгоритмы индексирования.

3. Алгоритм плавной локальной навигации по смежным фрагментам изображения.

4. Программная система визуализации графических файлов в формате HP-GL.

5. Экспериментальное исследование предложенных технологий визуализации болыпеформатных картографических документов.

Практическая значимость научного исследования. В основу диссертационной работы положены результаты, полученные автором в ходе комплексных исследований НИИ ПМК, проводимых в рамках НИОКР Министерства образования и науки Российской Федерации, Федеральной службы геодезии и картографии России, Главного управления навигации и океанографии МО Российской Федерации. Работа выполнена при финансовой поддержке РФФИ (проект № 05-01-00590).

Реализация результатов работы. Результаты диссертационной работы были использованы при разработке ряда версий систем контроля и подготовки

издательских материалов топографических и морских цифровых карт в НИИ ПМК.

Апробация работы. Материалы диссертации докладывались на следующих конференциях:

• научно-техническая конференция "ТЕКОМ-2004: Актуальные вопросы построения систем управления сложным распределённым оборудованием и предоставлением услуг" (Н. Новгород, Нижегородский гос. тех. ун-т, 2004),

• VIII Всероссийская научная конференция "Методы и средства обработки сложной графической информации" (Н.Новгород, Нижегородский гос. ун-т, 1216 сентября 2005),

• Всероссийская научно-техническая конференция ИСТ-2005 "Информационные системы и технологии" (Н. Новгород, Нижегородский гос. тех. ун-т, 2005),

• Всероссийская конференция "Технологии Microsoft в теории и практике программирования" (Нижний Новгород, Нижегородский гос. ун-т, 2006),

• Всероссийская конференция "Технологии Microsoft в теории и практике программирования" (Нижний Новгород, Нижегородский гос. ун-т, 2007),

• Всероссийская научно-техническая конференция "Информационные технологии в учебном процессе" (Н. Новгород, Нижегородский гос. тех. ун-т, 2007),

• Международная научно-техническая конференция ИСТ-2007 "Информационные системы и технологии " (Н.Новгород, Нижегородский гос. тех. ун-т, 2007),

• седьмая международная конференция-семинар "Высокопроизводительные параллельные вычисления на кластерных системах" (Н. Новгород, Нижегородский гос. ун-т, 2007),

• 9-th International Conference on Pattern Recognition and Image Analysis: New Information Technologies PRIA-9-2008 (Nizhni Novgorod, Nizhni Novgorod State University, Sept 14-20,2008),

• 20-я Международная конференция по компьютерной графике и зрению Графикон-2010 (Санкт-Петербург, Санкт-Петербургский гос. унт-т инф. технологий, механики и оптики, 21-25 сентября 2010).

Публикации. Результаты работы отражены в 16 научных публикациях, в том числе в трёх статьях, опубликованных в изданиях, рекомендованных ВАК.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы. Общий объем основного текста работы (без учёта списка литературы) - 134 машинописных страницы, список литературы включает 154 наименования.

Краткое содержание работы

Во введении дается общая содержательная постановка проблемы визуализации геоинформационных данных. Кратко изложены цели и содержание ра-

боты, перечислены результаты проведенных исследований, приведены данные об апробации и практическом использовании результатов.

Первая глава носит обзорный характер. В ней приводятся краткие исторические сведения о развитии отечественной картографии, описываются первые шаги, связанные с появлением цифровой картографии в нашей стране. Дается характеристика ведущих ГИС зарубежного и отечественного производства.

Среди ГИС, получивших во всем мире наибольшее распространение, отмечается продукция американской компании ESRI (Environmental Systems Research Institute), занимающейся разработкой серии таких программных продуктов, как ArcGis, ArcIMS, Arclnfo, ArcSDE, Arc View. К числу ГИС, наиболее популярных в России, относится Maplnfo Professional, официальным представителем разработчика которой в нашей стране является компания "ЭСТИ МАП".

В разделах 1.1 и 1.2 вводятся основные понятия и определения, связанные со спецификой представления данных о пространственных объектах, приводится классификация картографических объектов, описываются этапы создания электронных карт и их графических образов. Приводятся сведения о форматах хранения, обмена и обработки картографических данных. Описываются характеристики растровых, векторных и гибридных графических форматов представления изображений цифровых карт.

Особое внимание уделено автоматизированным картографическим системам, разработанным в НИИ ПМК, т.к. результаты диссертационной работы имеют непосредственную связь с системами отображения и подготовки издательских оригиналов цифровых карт, создаваемыми в этих АКС. Особенностью большинства АКС НИИ ПМК является использование для формирования графического образа картографических документов подмножества языка Hewlett-Packard Graphics Language (HP-GL), являющегося промышленным стандартом de-facto для производителей практически всех болынеформатных плоттеров.

Раздел 1.3 посвящен подсистемам визуализации цифровых карт, которые обеспечивают интерфейс с пользователями ГИС и особенно важны при наполнении специализированных баз данных, контроле полноты и качества их содержания и обновлении картографических данных. Сложность задач, решаемых визуализаторами, заключается в больших объемах графических данных (размер векторного графического файла достигает 100 Мб) и жестких временных ограничениях на работу алгоритмов фрагментации и масштабирования отображаемых участков цифровых карт (приемлемое время отображения одного кадра -порядка 1 секунды).

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

ваний, часто цитируемых в литературе по машинной графике. К числу самых известных методов отсечения отрезка относятся алгоритмы Коэна-Сазерленда, Цируса-Бека, Собкова-Поспишила-Янга и Лианга-Барски. Среди новых подходов, ориентированных на решение задачи отсечения в условиях массовой обработки ребер полигонов, отмечается алгоритм Ю.Л.Кеткова. Его основная идея заключается в том, что начало очередного ребра ломаной совпадает с концом предшествующего ребра, и результатами анализа предыдущего шага можно воспользоваться. Именно такая ситуация наблюдается в подавляющем большинстве графических команд языка НР-йЬ, используемого для формирования образов электронных карт.

Вторая глава посвящена методам и средствам повышения производительности визуализатора большеформатных графических документов, подготовленных в формате НР-вЬ.

В разделах 2.1 и 2.2 рассматриваются вопросы предварительной обработки графической информации. Важным этапом обработки исходного документа является изменение формата данных с целью сокращения объёма графической информации и повышения эффективности перебора графических записей в дальнейшем. На этом этапе двухбайтовые коды мнемонических графических команд заменяются "указателями" на входы в блоки обработки соответствующих процедур. Цепочки последовательных команд движения пишущего узла с указанием единственной точки назначения (команды РО х,у;) заменяются на одну команду со списком координат всех точек соответствующей ломаной. Команды перемещения "пера" вдоль опорных точек линейных знаков, сформированные в абсолютных координатах, заменяются цепочкой команд движения в относительных координатах. Однако наибольший эффект от преобразования исходного графического файла достигается за счет преобразования значений числовых параметров графических команд из символьного представления в соответствующие машинные форматы. При этом экономится не только объем исходной информации, но и сокращается число машинных тактов, затрачиваемое на ее последующую обработку.

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

Основная идея этого подхода сводится к созданию эквивалентной иерархической структуры прямоугольных кластеров, в которых сгруппированы последовательные цепочки графических команд. Формирование кластеров выполняется с учётом ряда закономерностей использования НР-вЬ команд (в частности специфики команды БР, формирующей некоторую разновидность цветового слоя). Для каждой группы команд вычисляются минимальные окайм-

ляющие прямоугольники (MBR - Minimal Bounding Rectangle), определяющие границы кластера. По окончании процесса кластеризации формируется внутреннее представление пространственных данных, которое с формальной точки зрения является математической моделью местности, представленной в виде ориентированного графа со взвешенными вершинами. Использование этой модели существенно упрощает анализ взаимного положения объектов цифровой карты по отношению к окну просмотра, что в конечном счёте существенно влияет на скорость визуализации.

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

В разделах 2.3 и 2.6 показывается, что одним из радикальных средств, обеспечивающих повышение производительности визуализатора, является индексация графических данных, которая позволяет резко сократить время на поиск объектов, принадлежащих заданному окну отображения. В случае индексирования данных внутреннего формата отбор объектов может выполняться как динамически (при каждом изменении масштаба изображения), так и статически (заранее, однократно) на базе начального разбиения. Второй подход подразумевает, что при первоначальном открытии документа выполняется разбиение всей сцены на прямоугольные подобласти (ячейки) и последующее индексирование документа производится относительно каждой из ячеек сетки. В результате для каждого графического объекта строится список ячеек, содержащих фрагменты объекта, а для каждой ячейки — список объектов, пересекающихся с ней. При этом отбор объектов выполняется статически, однократно. При последующем масштабировании и навигации по документу отбор как таковой не выполняется. Вместо этого для каждого окна масштабирования определяется список инцидентных ячеек, и множество отображаемых объектов строится путём простого объединения списков объектов для каждой инцидентной ячейки.

В работе показано, что динамический подход представляется более адекватным для задач контроля качества большеформатных документов, т.к. именно динамический подход позволяет совмещать приемлемую точность визуализации с высокой производительностью и адаптируемостью по отношению к входным данным. Кроме того, реализованная в работе технология кластеризации позволяет в некотором роде совместить базовые преимущества как статического, так и динамического подходов за счёт применения иерархического индексирования. Принцип иерархической фрагментации является ещё одним базовым принципом индексирования, использованным в работе. Его суть заключается в том, что результаты анализа/индексирования крупномасштабного родительского объекта можно применить при индексировании его дочерних объектов меньшего размера (меньшей площади, периметра). Это позволяет существенно уменьшить вычислительные затраты на этапе индексирования. С точки зрения технической реализации иерархическое индексирование подразумевает

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

Раздел 2.4 посвящен авторской модификации алгоритма массового отсечения ребер полигона, предложенного Ю.Л.Кетковым. Этот алгоритм позволяет значительно ускорить процедуру индексации самых элементарных примитивов - отрезков прямых. Показано, что за счет введения матрицы индексации областей изображения размерности 9x9, в 50 случаях из 81 возможного процедура индексации требует выполнения единственной операции сравнения. Лишь при анализе пересечения отрезка с горизонтальными и вертикальными прямыми требуется выполнить дополнительно восемь арифметических операций и 1-2 операции сравнения.

В разделе 2.5 отмечается, что система окаймляющих прямоугольников (МВЯ), формируемая на стадии предварительной обработки исходного файла, используется не только при формировании индексов различного уровня. Она упрощает принятие решений по поводу отображения тех или иных графических примитивов подобно некоторым операторам генерализации пространственных данных.

В разделе 2.8 описан алгоритм, позволяющий на 25-30% поднять производительность системы визуализации при плавном перемещении по соседним участкам карты. Он базируется на том факте, что редактор, оценивая полноту и качество электронной карты, выполняет регулярные перемещения по ее площади либо в горизонтальном, либо в вертикальном направлении. Поэтому при отображении смежного участка имеется возможность сохранить от 1/4 до 1/3 предшествующего изображения. Это сокращает время подготовки очередного кадра и приводит к более плавным переходам при навигации по смежным участкам цифрового изображения.

В связи с широким распространением ПК на базе многоядерных процессоров, немалый интерес представляют параллельные модификации алгоритмов визуализации. Этой области исследования посвящен раздел 2.9, где последовательно рассматривается два алгоритма с декомпозицией по данным и один алгоритм с функциональной декомпозицией процесса визуализации. Автором предлагается использовать конвейерную схему функциональной декомпозиции алгоритма, поскольку в отличие от других подходов "конвейерный" алгоритм эффективно функционирует независимо от целевой аппаратно-программной платформы и как правило не требует заметной реорганизации вычислений.

Третья глава посвящена вопросам проектирования и реализации визуа-лизатора электронных карт в формате НР-ОЬ. Главными требованиями, предъявляемыми к визуализатору РгеУесЮг, являются:

• четкое разделение функций главных модулей системы,

• ориентация на полное соблюдение правил и требований объектно-ориентированного подхода,

• адекватное применение объектно-ориентированных шаблонов проектирования,

• исследование узких мест, сдерживающих производительность системы с помощью лучших систем профилирования от ведущих производителей (AutomatedQA AQTime, Intel VTune Performance Analyzer),

• обеспечение масштабируемости компонент визуализатора и их переносимости на другие платформы (Windows Vista, Windows 7).

В современной версии визуализатора процесс обработки цифровой карты подразделяется на два основных этапа, выполняемых двумя функционально разными подсистемами. Первый этап, включающий предобработку исходных данных и формирование внутреннего формата представлений векторного описания электронной карты, выполняется подсистемой Parser. Второй этап, обеспечивающий различные уровни индексации элементов внутреннего формата и их визуализацию по заказу пользователя, выполняется подсистемой Process. Интерфейс между обеими подсистемами и интерактивное взаимодействие с пользователем обеспечивается третьей подсистемой - Userlnterface (сокращенно - UI). Схема взаимодействия подсистем приведена на рисунке 1.

UI

MapView

Wain Frame Navigator

ConfigView

Process

MapTransformatton

Path Command

i

Рисунок 1 - Взаимодействие компонент системы PreVector

Подсистема UI реализована на основе технологии MVC (Model-ViewController) с использованием графических элементов свободно распространяемой библиотеки шаблонов WTL (Windows Templates Library). В организации двух других подсистем - Parser и Process - существенную роль сыграли два

11

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

Основу подсистемы Parser составил шаблон проектирования Builder (Строитель), который позволил отделить процесс синтаксического анализа входных данных от процесса создания внутреннего представления сложного объекта. Шаблон "Компоновщик", также задействованный в процессе проектирования, обеспечил дополнительную гибкость программной системы, позволяя эффективно комбинировать различные приёмы индексирования в рамках одной структуры данных.

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

С целью снижения накладных расходов, связанных с выделением динамической памяти под вновь создаваемые объекты, было введено жесткое правило - обработка объектов одного типа должна быть отделена от обработки другого типа. Это позволило избежать излишней фрагментации динамической памяти и кардинально снизить число затратных по времени системных вызовов. Для реализации этой идеи был создан специальный класс PreVAllocator, алгоритм работы которого использовал ряд эвристик, основанных на предварительном исследовании файла с исходными данными. Использование нестандартного распределителя памяти позволило существенно снизить время, затрачиваемое на построение внутреннего формата. По результатам профилирования до 80% времени работы основного модуля BuildMapSequence тратилось на обращение к оператору new. После внедрения класса PreVAllocator доля вычислительных затрат, связанных с динамическим распределением памяти, сократилась до 10 -15%.

Четвёртая глава посвящена исследованию производительности разработанного визуализатора PreVector и сравнению его характеристик с возможностями зарубежных коммерческих разработок аналогичного плана. В качестве конкурирующих программных продуктов представлены пакет SPLOT32 (версии 4.10 и 5.01), приобретенный по лицензии и эксплуатируемый в НИИ ПМК в составе комплекса КАРТ-ДОК, и программное обеспечение ViewCom-panion (полнофункциональная пробная версия Premium 5.30). В качестве типовых цифровых карт при оценке эффективности визуализаторов использовались топографическая карта Новгородской области и две морские навигационные карты побережья Северного моря. Дополнительная цель исследования

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

Основной эксплуатационный режим использования каждого визуализа-тора заключается в многократном просмотре редактором-картографом фрагментов цифровой карты при достаточно большом увеличении на экране дисплея. При этом для листа карты среднего размера (формат А1) в общей сложности приходится просматривать порядка 600 фрагментов с коэффициентом увеличения от 4 до 8. В связи с этим сеанс работы с визуализатором естественно распадается на две фазы. Первый этап связан с инициализацией - начальной обработкой исходного графического файла, формированием различных управляющих таблиц и созданием уменьшенной растровой копии просматриваемого документа на экране. После этого редактор приступает к методическому просмотру фрагментов запланированной области. Наиболее характерными операциями второй фазы являются перемещения по смежным фрагментам карты с возможным изменением коэффициента масштабирования (как в сторону увеличения, так и в сторону уменьшения). Для усреднения временных характеристик каждого эксперимента моделировалось по 100 запросов к каждому визуализатору.

В ходе экспериментального исследования стадию инициализации быстрее всех завершал пакет SPLOT32. Второе место по результатам экспериментов занял Pre Vector, опережая пакет ViewCompanion Premium примерно в 2—4 раза (рисунок 2, замеры выполнялись для нескольких навигационных карт различного объёма и сложности). Однако инициализация выполняется однократно и проигрыш на первом этапе не является определяющим.

В фазе интерактивной навигации по смежным фрагментам карты Рге-Vector опередил аналоги с большим отрывом: время отклика на выполнение большинства массовых операций оказывалось на порядок меньше, чем у конкурентов. Некоторое представление о времени отклика при оперативной навигации с изменением масштабирующего коэффициента дают графики усредненных замеров, выполненные на одной из морских карт (рисунок 3). Конечно, к этим результатам следует относиться с некоторой осторожностью, поскольку невозможно провести абсолютно точное сравнение программных продуктов, два из которых являются "черными ящиками" (исходные коды фирмы-разработчики не предоставляют).

Результаты второго этапа исследования производительности визуализа-тора можно сформулировать следующим образом.

• Пространственная индексация (с использованием метода окаймляющих прямоугольников) позволяет существенно ускорить визуализацию при коэффициенте масштабирования более 2 за счёт быстрого отсечения протяжённых объектов, обеспечивая повышение производительности более чем в 5 раз.

• Алгоритм генерализации обеспечивает прирост производительности только при малых коэффициентах масштабирования за счёт исключения небольших пространственных объектов, различимых лишь при трёхкратном или большем увеличении.

14000

12000

10000

1

8 8000

1 6000 x oc £

m

4000

2000

|

1

i 1 |

/ 1

!

г к

i 1 1 ! i !

-ПО PreVector

-SPLOT32

—$™-ViewCompanioii Premium

4,5

12,8

28,0

39,2

19,5 Объём данных

Рисунок 2 - Время отклика при первоначальном открытии изображения. 14000

10000

S 6000 «

г

(У

m 4000

2000

"•v. I : ■ : ! j

% \ —И—ПО PreV/ector

\ \ -«$—viewCompanion

./ ; Premium j -SPLOT52

I ^ч! ! ; ! ! i

1,00

1,50

2,00

3,00

4,00

8,00

Масштабный коэффициент

Рисунок 3 - Время отклика при интерактивной навигации и оперативном изменении масштабирующего коэффициента.

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

Распараллеливание визуализации позволяет дополнительно повысить эффективность алгоритма визуализации на 10% - 25% практически при всех масштабных коэффициентах. Однако при 8-кратном увеличении полученный выигрыш уравновешивается накладными расходами, связанными с организацией многопоточных вычислений.

Основные результаты

• Разработана иерархическая кластерная модель внутреннего представления большеформатных цифровых карт на языке HP-GL, обеспечивающая компактное представление пространственной информации и повышающая оперативность ее последующей обработки. Предложен метод построения кластерной модели и формирования на её основе внутреннего формата графических данных.

• Предложены алгоритмы иерархической, статической и динамической индексации категорий графических объектов и исследовано их влияние на производительность системы оперативного отображения электронных карт.

• Исследованы классические и разработаны оригинальные алгоритмы, повышающие на 30-50% скорость выполнения графических операций, определяющих оперативное отображения цифровых карт.

• Разработан импортозамещающий программный продукт - система визуализации цифровых карт, представленных в формате промышленного стандарта Hewlett-Packard Graphics Language. По оперативности отображения разработанный визуализатор не уступает лучшим зарубежным аналогам, а по ряду показателей существенно их превосходит.

Публикации по теме диссертационной работы

Статьи, опубликованные в изданиях, рекомендованных ВАК

1. Матвеев, 3. А. Методы повышения эффективности систем воспроизведения картографических документов / 3. А. Матвеев, Ю. JI. Кетков // Вестник Нижегородского университета им. Н. И. Лобачевского. - Н. Новгород, 2008. -№2.-С. 138-146.

2. Матвеев, 3. А. Автоматическое создание кластерной модели графического образа электронных карт в формате HP-GL ! 3. А. Матвеев, Ю. Л. Кетков // Приволжский научный журнал. — Н. Новгород, 2011. - № 1. - С. 3 7-41.

3. Матвеев, 3. А. Разработка и исследование алгоритмов визуализации цифровых карт в векторном формате / З.А Матвеев, Ю.Л. Кетков // Приволжский научный журнал. - Н. Новгород, 2011. - № 2. - С. 45-49.

Другие публикации

4. Матвеев, 3. А. Решение задачи оптимизации просмотра файлов в векторном формате HPGL / 3. А. Матвеев // ТЕКОМ-2004: Актуальные вопросы построения систем управления сложным распределённым оборудованием и предоставлением услуг : материалы науч.-тех. конф. / Нижегор. гос. техн. ун-т. - Н. Новгород, 2004. - С. 59-60.

5. Матвеев, 3. А. О некоторых алгоритмах просмотра цифровых карт в формате HPGL I 3. А. Матвеев II Труды Нижегородского государственного университета. - Н. Новгород, 2005. - Т. 56. - С. 56-62.

6. Матвеев, 3. А. Использование алгоритмов индексирования при работе с цифровыми картам / 3. А. Матвеев // Методы и средства обработки сложной графической информации : тез. докл. VIII Всерос. науч. конф. / Нижегор. гос. ун-т им. Н. И. Лобачевского. - Н. Новгород, 2005. - С. 84-87.

7. Матвеев, 3. А. Решение задачи оптимизации просмотра электронной карты в векторном формате HPGL / 3. А. Матвеев // ИСТ-2005 "Информационные системы и технологии" : тез. докл. Всерос. науч.-техн. конф. / Нижегор. гос. техн. ун-т. - Н. Новгород, 2005. - С. 147.

8. Матвеев, 3. А. О некоторых задачах разработки программного обеспечения просмотра электронных карт / 3. А. Матвеев // Известия Академии инженерных наук им. А. М. Прохорова. Бизнес-Информатика. - 2006. - Т. 17. - С. 310.

9. Матвеев, 3. А. Применение внутренних форматов хранения графических данных при решении задачи просмотра точных электронных карт / 3. А. Матвеев II Технологии Microsoft в теории и практике программирования : материалы Всерос. конф. / Нижегор. гос. ун-т им. Н. И. Лобачевского. - Н. Новгород, 2006. - С. 210-213.

10. Матвеев, 3. А. Проектирование и принципы построения приложений предназначенных для обработки электронных карт / 3. А. Матвеев II Технологии Microsoft в теории и практике программирования : материалы Всерос. конф. / Нижегор. гос. ун-т им. Н. И. Лобачевского. - Н. Новгород, 2007. - С. 176-177.

11. Матвеев, 3. А. Разработка программного обеспечения просмотра электронных карт в рамках изучения и создания отечественных геоинформационных систем / 3. А. Матвеев // Информационные технологии в учебном процессе и активные методы обучения : материалы Всерос. науч.-методич. конф. / Нижегор. гос. техн. ун-т. - Н. Новгород, 2007. - С. 81-85.

12. Матвеев, 3. А. Особенности программной архитектуры приложений, предназначенных для обработки большеформатных графических документов / 3. А. Матвеев II ИСТ-2007 "Информационные системы и технологии" : материалы междунар. науч.-тех. конф. / Нижегор. гос. техн. ун-т. - Н. Новгород, 2007.-С. 159-161.

13. Матвеев, 3. А. О некоторой параллельной модификации алгоритма отображения фрагмента электронной карты / 3. А. Матвеев // Высокопроизводительные параллельные вычисления на кластерных системах : материалы 7-й междунар. конф.-семинара / Нижегор. гос. ун-т им. Н. И. Лобачевского. - Н. Новгород, 2007. - С. 392-397.

14. Матвеев, 3. А. Иерархическое индексирование электронных карт как отражение процесса моделирования предметной области / 3. А. Матвеев // Модели, методы и программные средства : тр. конф. учеб.-науч. инновац. ком-

плекса / Нижегор. гос. ун-т им. Н. И. Лобачевского. - Н. Новгород, 2007. - С. 279-281.

15. Matveev, Z. Indices Organization as Visualization System Performance Improvements Means / Z. Matveev // 9-th International Conference on Pattern Recognition and Image Analysis: New Information Technologies PRIA-9-2008 : conf. proceedings. -N. Novgorod, 2008. - Vol. 2. - P. 15-17.

16. Матвеев, 3. А. Анализ алгоритмов оптимизации времени отображения электронных карт в формате HP-GL / Ю. JI. Кетков, 3. А. Матвеев // Графикон-2010 : тр. 20-й междунар. конф. по компьютерной графике и зрению / С.-Петерб. гос. ун-т информ. технологий, механики и оптики. - СПб., 2010. - С. 246-252.

Подписано в печать /б'-О.Г, //< >~< Формат 60x90 1/16 Бумага газетная. Печать трафаретная. Объем 1 печ.л. Тираж 100 экз. Заказ № /67

Нижегородский государственный архитектурно-строительный университет, 603950, Н. Новгород, Ильинская, 65 Полиграфический центр ННГАСУ, 603950, Н.Новгород, Ильинская, 65

ВВЕДЕНИЕ

ГЛАВА 1. ГИС И ЗАДАЧА ВИЗУАЛИЗАЦИИ (ОБЗОР).

1.1 Традиционные и цифровые карты.

1.2 Обзор отечественных и зарубежных ГИС.л.

1.3 Форматы представления географических данных.

1.4 Визуализация картографических данных.

1.4.1 Оптимизационные задачи дискретной геометрии.

Выводы.

ГЛАВА 2. МЕТОДЫ И СРЕДСТВА ПОВЫШЕНИЯ ОПЕРАТИВНОСТИ СИСТЕМЫ ВИЗУАЛИЗАЦИИ ВЕКТОРНЫХ КАРТ.

2.1 Предварительная обработка исходных данных.

2.1.1 Сокращение объема исходного графического файла.

2'. 1.2 Классификация графических примитивов и их подмножеств.

2.1.3 Внедрение семантики в графику.

2.2 Внутренний формат как математическая модель пространственных данных

2.3 Индексация отображаемых объектов.

2.3.1 Статическая и динамическая индексация.

2.3.2 Метод окаймляющих прямоугольников.

2.3.3 Иерархическая индексация.

2.3.4 Повторная индексация.

2.4 Оптимизация алгоритма массового отсечения отрезков.

2.5 Генерализация отображаемых объектов.

2.6 Совместное использование различных приёмов индексации.

2.7 Алгоритмы преобразования координат векторного документа.

2.8 Оптимизация алгоритма локальной навигации.

2.9 Использование многоядерных процессоров.

Выводы.

ГЛАВА 3. ПРОЕКТИРОВАНИЕ И РЕАЛИЗАЦИЯ ВИЗУАЛИЗАТОРА ВЕКТОРНЫХ КАРТ.

3.1 Основные компоненты системы визуализации.

3.2 Применение шаблонов проектирования.

3.3 Применение пользовательского распределителя динамической памяти.

Выводы.

ГЛАВА 4. ИССЛЕДОВАНИЕ ПРОИЗВОДИТЕЛЬНОСТИ РАЗРАБОТАННОГО ВИЗУАЛИЗАТОРА.

4.1 Методика оценки производительности.

4.2 Анализ экспериментальных данных.

Выводы.

Актуальность работы. Современная экономическая, управленческая и исследовательская деятельность человека тесно связана с анализом пространственного положения объектов земной поверхности. Такого рода сведения необходимы при решении широкого спектра задач. Это - управление наземным, воздушным и водным транспортом, проектирование, разработка и эксплуатация различных коммуникаций, гражданское строительство и управление коммунальным хозяйством, землеустройство и экология, разведка полезных ископаемых, оборонная деятельность и многое другое.

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

В настоящее время существует множество автоматических и автоматизированных картографических систем (АКС), использующих различного рода программные и аппаратные средства, ориентированные на работу с геоинформационными данными. Такие комплексы обеспечивают сбор, редактирование, хранение, оперативную визуализацию и распространение пространственной информации в виде электронных карт или их твердых копий. Описание цифровой карты на ту или иную территорию земной поверхности, хранящееся в специализированной базе картографических данных (СБКД), представляет собой совокупность сведений о пространственных объектах двух видов: геометрических (позиционных) и атрибутивных {семантических). Геометрическая часть отражает геометрию объекта (указание положения объекта, элементы графического оформления), а атрибутивная содержит характеристики объектов (их качественные или количественные параметры) и пространственно-логические связи между ними.

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

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

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

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

Предметом исследования являются алгоритмы и средства повышения производительности систем отображения графических файлов формата НР-ОЬ.

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

Для достижения поставленной цели требуется решение следующих основных научных и практических задач:

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

Исследование внутренних форматов и математических моделей местности, используемых для представления графических образов электронных карт.

Разработка алгоритмов предварительной обработки исходного графического описания и индексирования групп графических операторов.

Разработка алгоритмов масштабирования и плавной локальной навигации между смежными фрагментами цифровых карт.

Применение оптимального алгоритма отсечения отрезков в задачах массовой обработки операторов линейного перемещения пишущего узла.

Анализ возможностей распараллеливания вычислительного процесса визуализации.

Реализация разработанных алгоритмов в виде программной подсистемы визуализации графических файлов формата HP-GL.

Экспериментальное сравнение производительности разработанной подсистемы с зарубежными аналогами.

Методы исследования. Теоретические исследования выполнены с использованием методов дискретной математики (теории графов, математической логики), вычислительной геометрии, компьютерной графики.

Экспериментальные исследования выполнены с помощью разработанной подсистемы визуализации, ряда отечественных АКС и известных визуализаторов SPLOT32 и View Companion (Premium) for Windows.

Достоверность и обоснованность полученных в работе результатов и выводов подтверждаются положительными результатами проведенных экспериментальных исследований и опытной апробации подсистемы, визуализации на ряде картографических документов, подготовленных в научно-исследовательском институте прикладной математики и кибернетики Нижегородского государственного университета им. Н.И. Лобачевского (НИИ ПМК).

Научная новизна состоит в том, что:

• предложены алгоритмы предварительной обработки графического файла в формате HP-GL, обеспечивающие автоматическое создание иерархической кластерной модели исходного файла;

• разработан внутренний формат представления графических данных и серия алгоритмов его индексирования;

• предложен алгоритм плавной локальной навигации по смежным кадрам изображения, обеспечивающий повышение производительности процесса визуализации на 30%;

На защиту выносятся:

1. Алгоритмы предварительной обработки исходного изображения.

2. Внутренний формат графических данных и алгоритмы индексирования.

3. Алгоритм плавной локальной навигации по смежным фрагментам изображения.

4. Программная система визуализации графических файлов в формате HP-GL.

5. Экспериментальное исследование предложенных технологий визуализации большеформатных картографических документов.

Практическая значимость научного исследования. В основу диссертационной работы положены результаты, полученные автором в ходе комплексных исследований НИИ ПМК, проводимых в рамках НИОКР Министерства образования и науки Российской Федерации, Федеральной службы геодезии и картографии России, Главного управления навигации и океанографии МО Российской Федерации. Работа выполнена при финансовой поддержке РФФИ (проект № 05-01-00590).

Реализация результатов работы. Результаты диссертационной работы были использованы при разработке ряда версий систем контроля и подготовки издательских материалов топографических и морских цифровых карт в НИИ ПМК.

Апробация работы. Материалы диссертации докладывались на следующих конференциях:

• научно-техническая конференция "ТЕКОМ-2004: Актуальные вопросы построения систем управления сложным распределённым оборудованием и предоставлением услуг" (Н. Новгород, Нижегородский гос. тех. ун-т, 2004),

• VIII Всероссийская научная конференция "Методы и средства обработки сложной графической информации" (Н.Новгород, Нижегородский гос. ун-т, 12-16 сентября 2005),

• Всероссийская научно-техническая конференция ИСТ-2005 "Информационные системы и технологии" (Н. Новгород, Нижегородский гос. тех. ун-т, 2005),

• - Всероссийская конференция "Технологии Microsoft в теории и практике программирования" (Нижний Новгород, Нижегородский гос. ун-т, 2006),

• Всероссийская конференция "Технологии Microsoft в теории и практике программирования" (Нижний Новгород, Нижегородский гос. ун-т, 2007),

• Всероссийская научно-техническая конференция "Информационные технологии в учебном процессе" (Н. Новгород, Нижегородский гос. тех. ун-т, 2007),

•■ Международная научно-техническая конференция ИСТ-2007 "Информационные системы и технологии " (Н.Новгород, Нижегородский гос. тех. ун-т, 2007),

• седьмая международная конференция-семинар "Высокопроизводительные параллельные вычисления на кластерных системах" (Н. Новгород, Нижегородский гос. ун-т, 2007),

• 9-th International Conference on Pattern Recognition and Image Analysis: New Information Technologies PRIA-9-2008 (Nizhni Novgorod, Nizhni Novgorod State University, Sept. 14-20, 2008),

• 20-я Международная конференция по компьютерной графике и зрению Графикон-2010 (Санкт-Петербург, Санкт-Петербургский гос. унт-т инф. технологий, механики и оптики, 21-25 сентября 2010).

Публикации. Результаты работы отражены в 16 научных публикациях, в том числе в трёх статьях, опубликованных в изданиях, рекомендованных ВАК.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы. Общий объем основного текста работы (без учёта списка литературы) - 134 машинописных страницы, список литературы включает 154 наименования.

Выводы

1. Проведено экспериментальное сравнение производительности разработанного комплекса PreVector по времени выполнения массовых заявок на визуализацию фрагментов реальных топографических и морских навигационных карт с наиболее известными зарубежными аналогами — комплексами SPLOT32 (Чехия) и ViewCompanion (Норвегия).

2. На этапе предварительной обработки комплекс PreVector уступил по времени чешскому аналогу, но оказался примерно в 3-4 раза быстрее норвежского визуализатора. Однако основные временные затраты при визуальном контроле полноты и качества электронных карт приходятся на второй этап работы редактора-картографа. На этом этапе оперативность комплекса PreVector оказалась на один порядок выше показателей программного обеспечения SPLOT32 и ViewCompanion.

3. Алгоритмы и методы повышения производительности процесса отображения цифровых карт в формате HP-GL, представленные в рамках настоящей работы, были использованы при создании ряда АКС НИИ ПМК.

5. Заключение

В ходе исследования были достигнуты следующие основные результаты:

• Разработана иерархическая кластерная модель внутреннего представления болыпеформатных цифровых карт на языке HP-GL, обеспечивающая компактное представление пространственной информации и повышающая оперативность ее последующей обработки. Предложен метод построения кластерной модели и формирования на её основе внутреннего формата графических данных.

• Предложены алгоритмы иерархической, статической и динамической индексации категорий графических объектов и исследовано их влияние на производительность системы оперативного отображения электронных карт.

• Исследованы классические и разработаны оригинальные алгоритмы, повышающие на 30-50% скорость выполнения графических операций, определяющих оперативное отображения цифровых карт.

• Разработан импортозамещающий программный продукт - система визуализации цифровых карт, представленных в формате промышленного стандарта Hewlett-Packard Graphics Language. По оперативности отображения разработанный визуализатор не уступает лучшим зарубежным аналогам, а по ряду показателей существенно их превосходит.

1. Александреску, А. Современное проектирование на С++ Текст. : пер. с англ. / А. Александреску. М. : изд. дом Вильяме, 2008. — 336 с.

2. Аммерал, JI. Принципы программирования в машинной графике Текст. : пер. с англ. / JT. Аммерал. М. : Сол Систем, 1992. - 224 с.

3. Антипова, Р.И. Инструментальная подсистема для вывода картографической информации на ЕС ЭВМ Текст. / Р.И. Антипова [и др.] // Автоматизированная обработка сложной графической информации : сборник / Горьковский гос. ун-т. — Горький, 1987. — С. 31-39.

4. Антонов, A.C. Параллельное программирование с использованием технологии ОрепМР Текст. : учеб. пособие / A.C. Антонов — М. : Изд-во МГУ, 2009. 77 с.

5. Ахо, А. Построение и анализ вычислительных алгоритмов Текст. / А. Ахо, Дж. Хопкрофт, Дж. Ульман. М. : Мир, 1979. - 536 с.

6. Беклемищев, Д.В. Курс аналитической геометрии и линейной алгебры Текст. / Д.В'. Беклемищев. — 7-е изд., стереотипное М. : Высш. шк., 1998.-320 с.

7. Берлянт, A.M. Геоинформатика. Толковый словарь основных терминов -Текст. / A.M. Берлянт [и др.] ; под ред. A.M. Берлянта, A.B. Кошкарёва.- М. : ГИС-Ассоциация, 1999. 204 с.

8. Берлянт, А. М. Картография Текст. : учебник для вузов / A.M. Берлянт.- М. : Аспект Пресс, 2002. 336 с.

9. Ю.Билич, Ю. С. Проектирование м составление карт Текст. : учебник для вузов / Ю.С. Билич, А. С. Васмут. М. : Изд-во Недра, 1984. - 364 с.

10. Брусенцев, Виталий. GDI+: графика нового поколения. Часть 3. Построение векторных изображений Текст. / Виталий Брусенцев // RSDN Magazine. 2003. - №3. - С. 35-43.

11. Буч, Г. Язык UML. Руководство пользователя Текст. / Г. Буч, Дж. Рамбо, И. Якобсон. М : ДМК Пресс, 2007. - 496 с.

12. З.Васин, Ю.Г. Автоматизированная система обработки информации морских карт (АСОИМК) Текст. / Ю:Г. Васин [и др.] // Методы и средстваобработки сложной графической информации : тр. 3-й Всесоюзн. конф. / Горьковский гос. ун-т. Горький, 1988. - С. 87-89.

13. Васин, Ю.Г. Автоматизация-создания морских традиционных и цифровых навигационных карт Текст. / Ю.Г. Васин, C.B. Вальчук // Методы и средства обработки графической информации : сборник / Горьковский гос. ун-т. Горький, 1988. - С.57-77.

14. Васмут, A.C. Автоматизация и математические методы в картосостав-лении Текст. / A.C. Васмут, JI.M. Бугаевский , А.М. Портнов. М. : Недра, 1991.-392 с.

15. Вельтмандер, П.В1 Машинная графика Текст. : учебное пособие в 3-х кн. / П.В. Вельтмандер; Новосиб. гос. техн. ун-т. — Новосибирск : Изд-во Новосиб. гос. техн. ун-та, 1997. Кн. 2: Основные алгоритмы компьютерной графики. - 1997. — 187 с.

16. Верещака, T.B. Топографические карты. Научные основы содержания Текст. / Т.В. Верещака. М. : МАИК "Наука. Интерпериодика", 2002. -320 с.

17. Вирт, Н. Алгоритмы и структуры данных Текст. / Н.Вирт. -М. : Мир, 1989.-358 с.

18. Воеводин, В.В. Параллельные вычисления Текст. /В.В. Воеводин, Вл.В. Воеводин. СПб. :БХВ-Петербург, 2002. - 608 с.

19. Ву, М. OpenGL. Руководство по программированию Текст. / М. Ву, Т. Девис, Дж. Нейдер, Д. Шрайнер. 4-е изд. - СПб : Питер, 2006. - 624 с.

20. Гамма, Э. Приемы объектно-ориентированного проектирования: Паттерны проектирования Текст. : пер. с англ./ Э. Гамма, Р. Хелм, Р. Джонсон, Дж. Влиссидес. СПб : Питер, 2004. - 366 с.

21. Гергель, В.П. Теория и практика параллельных вычислений Текст. : учеб. пособие / В.П. Гергель. — М. : Интернет-Университет Информационных Технологий; БИНОМ: Лаборатория знаний, 2007. 423 с.

22. ГОСТ 28441-90. Картография цифровая. Термины и определения-Текст. -М. : Изд-во стандартов, 1990. — 8с.

23. Капралов, Е.Г. Геоинформатика Текст. : учебник для студентов вузов. В 2-х кн. Кн. 1 / Е.Г. Капралов [и др.] ; под. ред. B.C. Тикунова. — 2-е изд., перераб. и доп. М. : Академия, 2008. - 384 с.

24. Карпов, Ю. Г. Теория автоматов Текст. / Ю.Г. Карпов. СПб. : Питер, 2002. - 224 с.

25. Касьянов, В. Н. Методы построения трансляторов Текст. / В.Н. Касьянов, И.В. Поттосин. Новосибирск : Наука, 1986. - 344 с.

26. Кетков, Ю.Л. Технология изготовления шаблонов печатных плат на IBM PC Текст. / Ю.Л. Кетков, М.С. Казачкова // Известия Академии инженерных наук РФ. Т. 2 - Москва-Н. Новгород : Изд-во ННГУ, 2001. — С.111-125.

27. Кетков, Ю.Л. Подготовка издательских оригиналов с помощью фотоплоттера КОР А Л Текст. / Ю.Л. Кетков, А.И. Кузнецов // Сборник научных статей юбилейной научно-технической конференции факультета ВМК и НИИ ПМК / Нижегородский гос. ун-т. Н. Новгород, 2003.

28. Климов, A.C. Форматы графических файлов Текст. / A.C. Климов. — С.Петербург : ДиаСофт, 1995 480с.

29. Кнут, Д. Искусство программирования. В 3-х томах. Т. 1. Основные алгоритмы Текст. / Д. Кнут. 3-е изд. - М.: «Вильяме», 2006. - 720 с.

30. Комарчук, С.А. Разработка математического и программного обеспечения подсистемы представления пространственных данных в геоинформационных системах Текст. : дис. . канд. техн. наук : 05.13.11 / С.А. Комарчук. М., 2003. - 147 с.

31. Кормен, Т. Алгоритмы: построение и анализ Текст. / Т. Кормен, Ч. Лейзерсон, Р. Ривест. М. : МЦНМО, 1999. — 960 с.

32. Кошкарёв, A.B. Картография и геоинформатика: пути взаимодействия Текст. / A.B. Кошкарёв // Известия Академии наук СССР. Серия "География". 1990. -№1. - С. 32.

33. Ларман, К. Применение UML 2.0 и шаблонов проектирования. Введение в объектно-ориентированный анализ, проектирование и итеративную разработку Текст. / К. Ларман. М. : Вильяме, 2008. - 736с.

34. Ласло, М. Вычислительная геометрия и компьютерная графика на С++ Текст. / М. Ласло. М. : БИНОМ, 1997. - 304 с.

35. Лисицкий, Д. В. Основные принципы цифрового картографированияместности Текст. / Д.В. Лисицкий. М.: Недра, 1988. - 261 с.

36. Мальцев, А. И. Основы линейной алгебры Текст. : учеб. пособие для студентов ун-тов / А. И. Мальцев. 4-е изд., стереотип. - М. : "Наука", 1975.-400с.

37. Матвеев, З.А. Автоматическое создание кластерной модели графического образа электронных карт в формате HP-GL / 3. А. Матвеев, Ю. Л. Кетков // Приволжский научный журнал. Н. Новгород, 2011. - № 1. — С. 37-41

38. Матвеев З.А. Методы повышения эффективности систем воспроизведения картографических документов Текст. / З.А Матвеев, Ю.Л. Кетков // Вестник ННГУ. 2008. - № 2. - С. 138-146.

39. Матвеев, З.А. О некоторых алгоритмах просмотра цифровых карт в формате HPGL Текст. / З.А.Матвеев // Труды НГТУ. Информационные технологии. 2005. - Т.56. - С. 56-62.

40. Матвеев, 3. А. О некоторых задачах разработки программного обеспечения просмотра электронных карт Текст. / З.А. Матвеев // Известия

41. Академии инженерных наук им. A.M. Прохорова. Бизнес-Информатика. -2006.-Т. 17.-С. 3-10.

42. Матвеев, З.А. Разработка и исследование алгоритмов визуализации цифровых карт в векторном формате / З.А Матвеев, Ю.Л. Кетков // Приволжский научный журнал. Н. Новгород, 2011. - № 2. — С. 45-49.

43. Мозговой, М. В. Классика программирования: алгоритмы, языки, автоматы, компиляторы. Практический подход Текст. / М. В. Мозговой. — СПб. : Наука и Техника, 2006. 320 с.

44. Мюррей, Д.Д. Энциклопедия форматов графических файлов Текст. / Д. Д. Мюррей, У. ван Райпер. Киев : Изд. группа BHV, 1997. - 672 с.

45. Никулин, Е. А. Компьютерная геометрия и алгоритмы машинной графики Текст. / Е. А. Никулин. СПб. : БХВ-Петербург, 2003. - 560с.

46. Основы генерализации на общегеографических картах мелкого масштаба Текст. / под ред. Ю. В. Филиппова // Труды ЦНИГАиК. 1955. -Вып. 104.-336 с.

47. Поздняков, Д.В. Картографическое обеспечение проектирования магистральных трубопроводов и обустройства месторождений с использованием ГИС технологий Текст. : дис. канд. геогр. наук : 25.00.35 / Д.В. Поздняков. М., 2007. - 124 с.

48. Пол, P. AutoCAD 2007. Фирменное руководство от Autodesk: русская версия Текст. / Р. Пол, Дж. Фитцджеральд. М. : изд. Триумф, 2007. -944 с.

49. Поляков, А. Методы и алгоритмы компьютерной графики в примерах на Visual С++ Текст. / А. Поляков, В. Брусенцев. 2-е изд. - СПб : БХВ-Петербург, 2003. - 547 с.

50. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Текст. / Ф. Препарата; М. Шеймос. М.: Мир, 1989г. - 478с.

51. Рихтер, Д. Windows для профессионалов: создание эффективных Win32-пpилoжeний с учетом специфики 64-разрядной версии Windows Текст. : пер. с англ. / Д. Рихтер. 4-е изд. - СПб. : Питер; М. : Русская редакция; 2008. - 720 с.

52. Роджерс, Д. Математические основы машинной графики Текст. / Д. Роджерс, Адаме Дж. Изд. 2-е, доп. и перераб. - М.: Мир, 2001. - 604 с.

53. Романов, В. Ю. Популярные форматы файлов для хранения графических изображений на IBM PC Текст. / В.Ю. Романов. М. : Унитех, 1992.-320 с.

54. Салищев, К. А., Картография Текст. : учеб. для вузов / К. А. Салищев. Изд. 2-е, перераб. - М. : Недра, 1971. - 248 с.

55. Самардак, А. С. Геоинформационные системы Текст. : учеб. пособие / А. С. Самардак. Владивосток: ДВГУ, Тихоокеанский институт, 2005. -123 с.

56. Сван, Т. Форматы файлов Windows Текст. / Т. Сван. -М. : Бином, 1995.-258 с.

57. Скворцов, А. В. Алгоритмы построения триангуляции с ограничениями Текст. / А. В. Скворцов // Вычислительные методы и программирование. 2002. - Т.З. - С. 82-92.

58. Снук, Г. Создание ЗБ-ландшафтов в реальном времени с использованием С++ и DirectX 9 Текст. / Г. Снук. М.: КУДИЦ-Образ, 2006.

59. Страуструп, Б. Язык программирования С++ Текст. / Б. Страуструп. -М. : БИНОМ; СПб. : Невский Диалект, 2002. 1054 с.

60. Уилсон, М. С++: Практический подход к решению проблем программирования Текст. / М. Уилсон. М. : КУДИЦ-Образ, 2006. - 136 с.

61. Фаулер, М. Рефакторинг: улучшение существующего кода Текст. / М. Фаулер [и др.]. -М. : Символ-Плюс, 2007.

62. Фень, Ю. Программирование графики для Windows Текст. / Ю. Фень. — СПб. : Питер, 2002. 1072 с.

63. Фридман, А. С+. Алгоритмы и приемы программирования Текст. / А. Фридман [и др.]. М. : Бином-Пресс, 2003. - 560 с.

64. Халугин, Е.И. Цифровые карты Текст. / Е.И.Халугин, Е.А.Жаловский, Н.Д.Жданов; под общ. ред. Е.И.Халугина. М. : Недра,Л992. - 419 с.

65. Херн, Д. Компьютерная графика и стандарт OpenGL Текст. : пер. с англ. / Д. Херн, М.П. Бейкер. 3-е изд. - М. : Вильяме, 2005. - 1168 с.

66. Хилл Ф. OpenGL. Программирование компьютерной'графики Текст. — СПб.: Питер, 2002. 1082 с.

67. Шустров, Д. ГосГИСцентр. Цифровые карты Роскартографии в формате Arclnfo Текст. / Д: Шустров // ArcReview. 2001. - №1 (16). - С. 3 .

68. Элджер, Д. С++: библиотека программиста Текст. / Д. Элджер СПб : Питер, 1999.-260 с.

69. Энджел, Э. Интерактивная компьютерная графика. Вводный курс на базе OpenGL Текст. : пер. с англ. / Э. Энджел. 2-е изд. - М. : Издательский дом "Вильяме", 2001. - 592 с.

70. Abler, R. Spatial organization: The geographer's view of the. world Text. / R.Abler, J.S. Adams, P. Gould. London : Prentice-Hall, 1972. - 587p.

71. CadSoftTools. AB Viewer version 7. Electronic resource. : AB Viewer presentation. Режим; доступа:http://www.cadsofttools.com/download/abvieweren.ppsj свободный; — Загл. с экрана.

72. Arge, L. The Priority RTree: A Practically Efficient and WorstCase Optimal RTree Text. / L. Arge [et al.] // ACM Transactions on Algorithms. March . 2008.-Vol. 4.-No. 1.- Article 9.

73. Barsky, B.A. A new concept and method for line clipping Text. / B. A. Barsky, You-Dong Liang. // ACM Transaction on Graphics. January 1984. -Vol.3.-No. 1,-P: 1-22.

74. Beckmann, N. The R*-tree: An efficient and robust access method for points and rectangles;Text.;/N; Beckmann [et alQ//ACM'SIGMOD Int. Conf. on Management of Data : Proceedings. Atlantic City, 1990. - P. 322331.

75. Berry, J.K. Beyond Mapping: Concepts, Algorithms, and Issues in GIS . Text. / J.K. Berry. Ft. Collins, CO ; GIS World Books, 1993. - 246 p.

76. Chan, E. P.F. On Mülti-Scale Display of Geometric Objects Text. / E. P.F Chan, K. Chow // Data and Knowledge Engineering (DKE). 2002. -vol 40.-P. 91-119;

77. Chapman, В. Using OpenMP: portable Shared Memory Parallel Programming Text. / B. Chapman [et al.]. USA : MIT Press, 2007. - 353 p.

78. Chitre, Ameet. Engineering Windows 7 Grahphics performance Electronic resource. / Ameet Chitre. Режим доступа:http://blogs.msdn.com/e7/archive/2009/04/25/engineering-windows-7-for-graphics-performance.aspx., свободный. Загл. с экрана.

79. Cohen, А. Win32 Multithreaded programming Text. / A. Cohen, M. Woodring. USA : O'Reilly & Associates, Inc. 1997. - 724 p.

80. Cyrus, M. Generalized two- and three dimensional clipping Text. / M. Cyrus, J. Beck // Computer and Graphics. 1978. - vol. 3. - P. 23-28.

81. ESRI Shapefile Technical Description. An ESRI White Paper Electronic resource. Режим доступа:http://www.esri.com/library/whitepapers/pdfs/shapefile.pdf, свободный. -Загл. с экрана.

82. Gaede, V. Multidimensional Access Methods Text. / V. Gaede, O. Günther // ACM Computing Surveys. 1998. - Vol 30. - No 2. - P. 170231.

83. GeoDraw/Географ/Геоконструктор Программное обеспечение ЦГИ ИГ РАН: опыт и перспективы разработки Текст. // ГИС-Обозрение. — 1999.-№ 1.-С. 12-30.

84. Guting, R.H. An introduction to spatial database systems Text. / R.H. Gutting. VLDB Journal. - 1994. - Vol 3. - No 4. - P. 357-399.

85. Guttman, A. R-trees: A dynamic index structure for spatial searching Text. / A. Guttman // ACM SIGMOD Int. Conf. on Management of Data : proceeding. Minneapolis, 1984. - P. 47-54.

86. Han, Q. A Multi-level Data Structure for Vector Maps Text. / Q. Han, M. Bertolotto // ACMGIS-: Proceedings. Washington, 2004. - P. 214-221.

87. Harmon, J. E. The design and implementation of geographic information systems Text. / J. E. Harmon, J. A. Steven. NJ : John Wiley & Sons, Inc., 2003.-272 p.

88. ISO 19117:2005. Информация географическая. Представление Текст. : пер. с англ. -М. : Стандартинформ, 2005. 48 с.

89. Jackson Chris. GDI vs. GDI+ Text Rendering Performance Electronic resource. / Chris Jason. Режим доступа:http://blogs.msdn.com/cjacks/archive/2006/05/19/gdi-vs-gdi-text-rendering-performance.aspx, свободный. — Загл. с экрана.

90. Jain, A.K. Fundamentals of digital image processing Text. / A.K. Jain. — NJ : Prentice Hall, 1989. 592 p.

91. Koach, Geoff. Intel's road to multi-core chip architecture. Whitepaper. Electronic resource. / Geoff Koach. Режим доступа: cache-www.intel.com/cd/00/00/22/09/220997220997.pdf, свободный. - Загл. с экрана.

92. Koelma, D. A Software Architecture for Parallel Image Processing Text. / D. Koelma, H.J. Sips / Third Annual Conference of the Advanced School for Computing and Imaging : Proceedings. Heijen, 1997. - P. 34-40.

93. Larrabee: A Many-Core x86 Architecture for Visual Computing Text. // Seiler L. [et al.] // ACM Transactions on Graphics (TOG). 2008. - Vol 27. - Issue 3. - Article 18.

94. Lipeck, U. Modeling and Manipulating Objects in Geoscientific Databases Text. / K. Neumann, U. Lipeck // 5th Intl. Conf on the Entity-Relationship Approach: Proceedings. Dijon, 1987. - P. 67-86.

95. MS Windows NT Kernel-mode User and GDI White Paper Electronic resource. Режим доступа: http://technet.microsoft.com/ru-ru/library/cc750820(en-us).aspx, свободный. - Загл. с экрана.

96. Novy A. SPLOT Reference Guide for HP-GL/2 Electronic resource. / A. Novy. Режим доступа: http://www.splot.com , свободный — Загл. с экрана.

97. Novy A. SPlot V5.20 for Windows. User Guide Electronic resource. / A. Novy. Режим доступа: http://www.splot.com , свободный — Загл. с экрана.

98. О' Thuathail Eamon. WTL Developer Guide Electronic resource. / By Eeamon O' Thuathail (www.clipcode.biz). Режим доступа: http://filedb.experts-exchange.eom/incoming/2008/06w27/37211/Clipcode-WTL-Developer-Guide.pdf, свободный. - Загл. с экрана.

99. Open Design Specification for .dwg files Electronic resource. / Open Design Alliance. Version 4.0. - Режим доступа:http://www.opendesign.com/files/guestdownloads/OpenDesignSpecification for.dwgfiles.doc, свободный. — Загл. с экрана.

100. Orenstein, J. PROBE Spatial Data Modeling and Query Processing in an Image Database Application Text. / J. Orenstein, F. Manola // IEEE Trans, on Software Engineering. 1988. - Vol 14. - P 611-629.

101. Pagel, B.-U. Towards an Analysis of Range Query Performance in Spatial Data Structures Text. / B.-U. Pagel [et al.] // 12th ACM SIGACT-SIGMOD-SIGART Symp. Principles of Database Systems: Proceedings. Washington, 1993.-P. 214-221.

102. Quinn, M. J. Parallel Programming in С with MPI and OpenMP Text. / M. J. Quinn. New York : McGraw-Hill, 2004. - 544 p.

103. Ravikanth, V. Pro Oracle Spatial for Oracle Database 1 lg Text. / V. Ra-vikanth, A. Godfrind, E.K. Beinat. NY : APress, 2007. - 787p.

104. Reinders, James. VTune™ Performance Analyzer Essentials. Measurment and Tuning Techniques for Software Developers Text. / James Rainders. — USA : Intel Press, 2005. 455 p.

105. Rodgers, D. P. Improvements in multiprocessor system design Text. / D. P. Rodgers // ACM SIGARCH Computer Architecture News archive. 1985. -Vol 13. - No 3. - P. 225-231.

106. Samet, H. Applications of Spatial Data Structures : Computer Graphics, Image Processing, and GIS Text. / H. Samet // MA: Addison-Wesley, 1989.-504 p.

107. Sobkow, M.S. A Fast Two-Dimensional Line Clipping Algorithm via Line Encoding Text. / M.S. Sobkow, P. Pospishil, Yee-Hong Yang // Computer & Graphics. 1987. - Vol. 11. - No. 4. - P. 459-467.

108. Suri, S. Analyzing Bounding Boxes for Object Intersection Text. / S. Suri, P. Hubbard , J. Hughes // ACM Transactions on Graphics. 1999. - vol 18.-No 3.-P. 257-277.

109. Sutherland, I.E. Reentrant Polygon Clipping Text. / I.E. Sutherland, G.W. Hodgman // Communications of the ACM. 1974. - vol 17. - No 1. -P. 32-42.

110. The HP-GL/2 and HP RTL reference guide: a handbook for program developers Text. / Hewlett-Packard. MA : Addison-Wesley, 1997. - 3rd edition. - 544 p.

111. Vasin, Yu.G., GIS Terra: A graphic database management system Text. / Yu.G. Vasin, Yu.V. Yasakov // International Conference on Pattern Recognition and Image Analysis: PRIA-5-2008 : proceedings. 2008. - vol. 14. - No 4.-P. 579-586.

112. View Companion. Premium Edition. Quick reference Electronic resource. / Software Companions. Режим доступа: http://www.softwarecompanions.com/viewpremium.html, свободный. — Загл. с экрана.

113. Ward, Michael К. The Microstation V8 Workbook: A Complete Educational and Training Guide for Mastering 2d Applications of Microstation V8 Text. / Paul S. Choi, Michael K. Ward. Champaign, Illinois : Stipes Publishing Lie, 2002. - 480 p.

114. Wilkinson, В. Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers Text. / M. Allen, B. Wilkinson. NJ : Prentice Hall, 2004. - 496 p.

115. Walbourn, C. Graphics APIs in Windows Vista Electronic resource. / C. Walbourn ; MSDN. Режим доступа: http://msdn.microsofi.com/en-us/library/bbl73477.aspx, свободный. — Загл. с экрана.

116. Weiler, К. Hidden Surface Removal Using Polygon Area Sorting Text. / K. Weiler, P. Atherton // SIGGGRAPH'77, Computer Graphics : Proceedings. San Jose, 1977.-Vol. 11.-N. 2.-P. 214-222.

117. Zhou, Y. Shape sensitive geometric permutations Text. / Y. Zhou, S. Suri // 12th ACM-SIAM Symposium Discrete Algorithms : Proceedings. Washington, 2001.-P. 234-243.