Написание алгоритма поиска и сортировки территорий равной высоты в картах высот на конкретной территории

Введение
      В современном мире персональные компьютеры стали неотъемлемой частью нашей жизни.  Они обладают огромным разнообразием возможностей при установке на них определенных программных средств (ПС). Благодаря этим ПС перед пользователями открывается возможность решать самые различные прикладные задачи. Большая часть программных средств являются универсальными, например, переводчики, компьютерные игры, карты, редакторы текста и изображений, и многие другие. Диапазон программных средств крайне обширен и напрямую зависит от конечных целей пользователей.
      Для создания различных изображений и анимаций, реалистичных либо напротив нереальных, прибегают к помощи специализированных программных средств, предназначенных для обработки и создания изображений, такие прикладные программы часто называют – генератор ландшафтов/рельефов. Именно они позволяют относительно быстро формировать картинки и анимации настолько реалистичные, что, когда смотришь на них, кажется, что, если провести по ним рукой, на пальцах останется утренняя роса или пустынный песок. Все зависит от идеи и конечной цели автора. Все эти «шедевры» написаны в жанре фотореализм и иногда просто невозможно отличить их от фотографий. 
      Аналогичные прикладные решения имеют все шансы получить высокую популярность совершенно в различных сферах жизни человека, их актуальности нет границ. В частности, при использовании генератора ландшафтов/рельефов появляется возможность превратить обычное изображение в маркетинговый баннер, фоновую страницу веб-сайта, визитку, во что угодно, результат может быть ограничен только фантазией разработчика. Также искусственные ландшафты очень часто берут за основу, при разработке 3D сцен, например, разработка всевозможных трехмерных видеоигр, рекламных роликов или музыкальных/видео роликов. 
      На ряду со всеми перечисленными областями применения, стоит отметить, еще одну, генератор ландшафтов/рельефов может стать реальным открытием для историков и ландшафтоведов, ведь историки – это именно те специалисты, которые занимаются исследованием документов, предметов и мест, имеющих отношение к прошлому человечества, а для ландшафтоведы, изучают строение, происхождение, функционирование и трансформацию земных ландшафтов. Специалистам в области истории и ландшафтоведения, искусственные ландшафты смогут помочь в создании имитационной модели любой части планеты в этот либо другой общеисторический этап жизни человечества, что в дальнейшем может стать наглядным учебным пособием. 
      Также работа с генераторами ландшафтов/рельефов не оставит равнодушными архитекторов, проектировщиков, строителей. Польза заключается в том, что люди этих профессий сумеют, проанализировав весь макет выбрать максимально подходящий участок для строительства определенных зданий и сооружений. Так же подобные макеты будут полезны туристам и людям, работающим в сфере доставки, так как они помогут любому человеку познакомиться с местностью и выбрать наиболее подходящий маршрут или место для отдыха. Полезными искусственные пейзажи так же могут оказаться для студентов ПетрГУ, например, для наглядного представления расположения учебных корпусов и общежитий.
      Невозможно ни отметить актуальность трехмерных ландшафтов, ведь сегодня они активно используются в современных популярных компьютерных играх, системах моделирования и навигаторах.
      Исходя из всего вышеописанного можно сделать вывод, что трехмерные ландшафты стали неотъемлемой частью современных игр, систем моделирования и навигации.
      Доказав актуальность прикладных программ для генерации ладшафтов, стоит выделить цели моей дипломной работы. Главная цель – это написание алгоритма поиска и сортировки территорий равной высоты в картах высот на конкретной территории. Для разработки данного алгоритма было необходимым изучить представление геоданных в топографических картах, а также возможности их чтения и визуального представления. 

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

Трехмерное представление рельефа
     Говоря о многомерном представлении рельефа в компьютерной графике, стоит обосновать понятие «трехмерная графика».
     В современном мире сложно встретить человека, который ни разу не сталкивался с таким понятием как трехмерная графика, большинство не только знают, что это такое, но и используют ее в повседневной жизни. Однако точно есть и такие люди, которые увидев аббревиатуру 3D не сразу поймут, о чем речь. 
     Трехмерная графика (3D Graphics, Три измерения изображения) – это раздел компьютерной графики, совокупность приемов и инструментов, предназначенных для изображения объёмных объектов. Больше всего применяется для создания изображений на плоскости экрана или листа печатной продукции в архитектурной визуализации, кинематографе, телевидении, компьютерных играх, печатной продукции, а также в науке и промышленности. 1
     Различие 2D от 3D изображений на примере: рельеф имеет три измерения, на самом деле в реальности все изображения являются трехмерными, однако фотография или рисунок рельефа будет иметь только два измерения. На фото или рисунке мы увидим и измерим лишь длину и высоту, в то время как глубина и толщина неразличимы.
     С целью получения 3D изображений на 2D плоскости необходимо пройти три этапа:
     1. Проектирование
     На этом этапе перед проектировщиком стоит цель – создать математическую 3D модель воображаемого пространства со своей геометрией, например, здания или сооружения, со своими материалами, например, цвет здания, и со своими дополнительными эффектами, например, природные условия. 
     
     
     
     2. Визуализация (рендеринг)
     Теперь перед проектировщиком ставится новая цель, а именно ему необходимо построить проекцию по, разработанной на предыдущем шаге, математической модели, которая, в свою очередь будет представлена картинкой в формате 2D. Это достигается путем представления картинки как матрицы точек, пикселей. Пожалуй, второй этап разработки 3D изображений можно считать самым трудным, в особенности при необходимости построения натурального, реалистичного изображения.
     3. Результат
     На последнем шаге от проектировщика требуется вывести результат на устройство вывода. 


Алгоритмы построения рельефа
      Перед тем как приступить к проектированию ландшафтов, следует определится с таким понятием как цифровая модель рельефа, в дальнейшем ЦРМ. ЦМР – это цифровое представление рельефа местности за исключением растительности, мостов и тому подобного, широкое применение ЦМР нашла в ГИС (географические информационные системы). Сейчас ЦМР считается самой используемой моделью предоставления информации.
      Топографические карты, атласы, снимки со спутников все это служит фундаментом для построения ЦМР.
      Выделяют две наиболее актуальные разновидности ЦМР: растровые и модели TIN.
      Так как данная дипломная работа ориентирована на знакомство именно с растровой ЦМР, стоит раскрыть ее особенности. 
      Растровая ЦМР представляет собой преобразованные исходные карты в растровые черно-белые изображения с расширением *.tif. 
      Проектировщик, поставивший перед собой цель – построить ЦМР самостоятельно, должен использовать набор данных, а именно: 
      1. Пикет.
      Пикет – точечный векторный объект, который располагается на поверхности рельефа.2
      2. Карта высот.
      Матрицей высот (DEM – Digital Elevation Model) – называют цифровое картографическое представление земной поверхности в виде регулярной сетки значений высот.3
      3. Нерегулярная пространственная сеть треугольников.
      Нерегулярная пространственная сеть треугольников используется при конструировании ЦМР, в виде высотных отметок в узлах нерегулярной сети треугольников. 4
      4. Посегметная карта высот.
      Алгоритм построения посегментной карты высот основан на алгоритме построения карт выcот, однако заместо сведений о величине высоты, хранятся сведения об показателях рельефных секторов.  
              
              




      Карты (матрицы) высот
      В предыдущем разделе было отмечено, что карта выcот служит для ЦКП (цифровое картографическое предложение) информации о земной поверхности, которые в свою очередь представляются «регулярной сеткой» со значениями высот. Благодаря регулярной сетке со значениями высот представляются данные, которые представляют собой двумерный массив, в котором величины a и b уже определены и соответствуют величинам географической долготы и широты соответственно, а координата c, соответствует величине высоты в конкретном элементе этого массива.

Рисунок 1. Матрица высот


Рисунок 2. Построенный рельеф
      Стандартно матрица выcот представляет собой растровое изображение, в котором значения a и b отмечают расположение определенного пикселя на рисунке, а значение c представляется одним из оттенков 256 градаций черного, следовательно, мы можем наблюдать прямую зависимостью оттенка от величины высоты над уровнем моря, чем выше величина высоты в точке, тем эта точка темнее и наоборот. Но на ряду с таким весомым достоинством, использования растровых изображений, как возможность представлять огромные территории, существует и недостаток – избыточность данных, немалое количество описаний для массива. 
      Невозможно не упомянуть и об остальных достоинствах использования матрицы высот:
      1. Наглядность
      Заключается в том, что содержимое данных карт высот можно раскрыть и изучить, используя лишь программу для просмотра и редактирования файлов графического формата.
      
      2. Простота
      Основана на той же возможности работы с программами для просмотра и редактирования файлов графического формата, но отмечается уже возможность редактирования растровых изображений.
     



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

   Рис. 2 Иррегулярная сетка

Посегментная карта высот
      Еще одним активно используемым способом построения рельефов является посегментная карта высот. Принцип работы данного алгоритмы аналогичен работе алгоритма карт высот, но заместо информации о значениях высот, хранится информация об индексах рельефных сегментов, которые могут быть как регулярными, так и иррегулярными.
      Ниже разберем достоинства и недостатки использования этого алгоритма.
      Самым главным преимуществом, собственно, как и у карты высот, является возможность представить пространства немалого объема. Так же появляется право на хранение не только информации о рельефе, но и дополнительной информации, такой как местоположение, занимаемая территория каких-либо объектов, например, зданий, деревьев, гор и так далее. На ряду со всем этим проектировщику предоставляется возможность выбора детализации создаваемого рельефа, а именно он может создавать различные версии в зависимости от скорости работы компьютера или его загруженности.
      Однако минусы тоже имеются, вот, например, данные предоставляемые этим алгоритмом не являются очевидными, то есть невозможно посмотрев на них моментально визуализировать рельеф, например, в компьютерной игре. Сложность модификации, если при использовании карт высот или иррегулярной сетки мы можем использовать готовое программные продукты, то для использования данного метода алгоритм для работы с ним необходимо будет написать самому проектировщику.
      Рассмотрев все достоинства и недостатки, принципы работы и представления данных существующих алгоритмов для разработки рельефа, следует выделить наиболее универсальный –  использование карт высот. В сравнении матрицы высот с другими существующими алгоритмами, необходимо выделить ее превосходство в использовании наименьшего количества времени при редактировании и реализации рельефа, а также удобство хранения данных, минимальное количество программных средств для работы с ней. 


    Получение данных
      В современном мире многие из нас активно пользуется онлайн картами, навигаторами, но мало кто может себе представить каким образом эти данные представляются. Данные о рельефе или высотах очень часто оказываются полезными для некоторых методов геоинформационного анализа.
      С целью получения необходимых для моей работы данных о высотах на определенной территории я использовала географическую информационную систему QGIS, которая в свою очередь идеально подходит для обработки данных высот. Но перед началом работы с географической информационной системой QGIS, необходимо найти и загрузить бесплатные доступные пространственные данные.
      Для получения необходимых данных был использован, один из основных и бесплатных источников материалов дистанционного зондирования Земли, архив геологической службы США United States Geological Survey, сокращено USGS, а именно сервис EarthExplorer [5].  Для получения данных необходимо пройти процедуру регистрации на официальном сайте геологической службы. Интерфейс достаточно удобный и понятный, основными элементами являются строка команд, благодаря пользователь может пройти процедуру авторизации или регистрации, панель поиска материалов предназначена для задания критериев поиска нужных материалов, и карта, занимающая основную часть страницы.
      Алгоритм работы для получения данных:
      1. Обязательная регистрация
      2. Ввод параметров для поиска необходимой территории
      3. Выбор набора данных, в нашем случае GMTED2010
      GMTED (Global Multiresolution Terrain Elevation Data) представляет собой глобальный набор данных о рельефе.
      4. Загрузка архива с данными
      необходимо перейти на сайт геологической службы США United States Geological Survey, сокращено USGS.  
(https://studfiles.net/preview/4584408/) – определение 3d изображений
http://www2.racurs.ru/download/docs/rus/DEM.pdf - наборы данных для создания ЦМР
https://otherreferats.allbest.ru/programming/00162036_0.html - первая глава
http://www.qgistutorials.com/ru/docs/working_with_terrain.html - работа с ЦРМ
1 https://studfiles.net/preview/1731843/page:2/
2 http://www2.racurs.ru/download/docs/rus/DEM.pdf
3 http://www2.racurs.ru/download/docs/rus/DEM.pdf
4 http://www2.racurs.ru/download/docs/rus/DEM.pdf
5 https://earthexplorer.usgs.gov/
---------------

------------------------------------------------------------

---------------

------------------------------------------------------------

.......................