Содержание к диссертации
Введение
Глава 1. Задачи видимости, возникающие при сканировании поверхности Земли, анализ существующих методов их решения 11
1.1 Радиолокационные системы бокового обзора 12
1.2 Задачи видимости в РЛС бокового обзора 16
1.3 Требования к методам решения задачи видимости в РЛС бокового обзора 21
1.4 Анализ существующих методов решения задачи видимости 22
1.4.1 Методы удаления скрытых линий и поверхностей 22
1.4.2 Методы расчёта освещения 26
1.4.3 Методы построения потенциально видимых множеств, решение задачи видимости для площадок-полигонов 28
1.4.4 Нахождение пронизывающих прямых 30
1.5 Решение одиночной задачи видимости существующими методами 38
1.5.1 Решение задачи видимости на плоскости 38
1.5.2 Решение задами видимости в пространстве 40
1.5.3 Использование комплекса видимости 41
1.6 Анализ возможности использования существующих методов определения видимости в рассматриваемых условиях 43
1.7 Выводы 46
Глава 2 Разработка метода решения задачи видимости на базе перехода в пространство отрезков видимости 48
2.1 Решение задачи видимости для точечных площадок 50
2.1.1 Видимость точка-точка 50
2.1 2 Видимость точка-отрезок 51
2.1.3 Видимость точка-полигон 57
2.2 Решение задачи видимости для произвольных площадок 62
2.2.1 Видимость отрезок-отрезок 62
2.2.2 Видимость отрезок-полигон 72
2.2.3 Видимость полигон-полигон 74
2.3 Обобщение алгоритма решения задачи видимости 77
2.4. Применение алгоритма для решения задачи видимости при сканировании поверхности Земли 81
2.5 Выводы 82
Глава 3 Разработка метода формирования проблемно-ориентированной цифровой карты местности для решения задачи видимости 83
3.1 Хранение информации о карте местности 84
3.2 Формирование заслонок и площадок для решения задачи видимости 91
3.3 Отсеивание лишних заслонок при решении единичной задачи видимости 93
3.4 Решение задачи видимости для двух отрезков в пространстве 94
3.5 Выводы 96
Глава 4 Пакет программ решения задачи видимости при сканировании земной поверхности: результаты эксперимента 97
4.1 Состав программного пакета 98
4.2 Характеристики программы расчета видимости 99
4.3 Оценка эффективности разработанного метода для решения задачи видимости 106
4.4 Внедрение разработанных методов и структур 114
4.5 Выводы 115
Заключение 116
Список использованной литературы 117
- Радиолокационные системы бокового обзора
- Видимость точка-отрезок
- Хранение информации о карте местности
- Характеристики программы расчета видимости
Введение к работе
Актуальность темы.
Задачу определения видимости приходится решать во многих ситуациях и областях. Например, определение видимости является одним из важных этапов при визуализации трёхмерных геометрических данных, когда необходимо определить, какие части трёхмерных объектов при проецировании на картинную плоскость (экран) окажутся заслонены от наблюдателя другими объектами. Как правило, геометрические объекты представляются набором многоугольников - полигонов. При кажущейся простоте, эта задача требует больших объёмов вычислений даже при небольшом количестве объектов, так как необходимо проверить каждый объект на заслонённость от наблюдателя всеми остальными объектами. Кроме визуализации, существуют и другие области, где требуется решать задачу определения видимости (далее - задачу видимости). Это освещение, распознавание геометрических фигур, управление роботами и так далее (подробное описание областей применения приведено в [49]). Например, при расчёте освещения нужно определить, освещается ли объект источником света или же он частично или полностью находится в тени от других объектов. Нужно отметить, что постановка задачи видимости в этом случае несколько отличается от той, что имеет место при визуализации. Для визуализации необходимо определить видимость некоторого объекта из некоторой точки (точки схода пучка проецирующих прямых), при этом каждая точка каждого объекта мохсет быть либо видима, либо невидима. Для расчёта освещения необходимо определять видимость между двумя объектами (источник света и освещаемый объект), каждый из которых имеет размер. В этом случае для каждой точки объекта не будет однозначного признака видимости источника света, часть точек источника света будет видима, часть -невидима.
Можно сформулировать задачу видимости следующим образом. Даны два множества точек А и В, между которыми необходимо определить видимость, и загораживающее множество точек Z, Точки КєА и QeB являются
взаимовидимыми, если (Rl +(1- l)Q) Z для VtG[0..1] , где R, Q - векторы из
начала координат в точки R и Q соответственно, t - некоторый параметр. То есть, если отрезок RQ не пересекает загораживающее множество. Между множествами точек А и В существует видимость, если существует хотя бы одна взаимовидимая пара точек ReA и QeB. Видимость является полной, если взаимовидима любая пара точек R^A и QgB. Множества, между которыми необходимо определить видимость, в дальнейшем будут называться площадками, загораживающие множества - заслонками, а отрезки RQ, соединяющие точки площадок - отрезками видимости. На плоскости в качестве площадок и заслонок обычно выступают либо точки, либо отрезки прямых, в трёхмерном пространстве к ним добавляются многоугольники. Таким образом, решение задачи видимости - это определение наличия видимости между площадками. Для одних задач достаточно определения самого факта наличия видимости, для других необходимо определить какие части площадок являются взаимовидимыми, для третьих - получить коэффициент видимости (отношение числа взаимовидимых пар точек на площадках к общему числу возможных пар).
Как отмечалось выше, задача видимости возникает в различных областях, и в зависимости от постановки задачи будут эффективны разные методы её решения. Например, для задач удаления скрытых линий и поверхностей используются одни методы, а для расчёта освещения - другие. В настоящей работе рассматривается задача видимосіи, возникающая при радиолокационном сканировании поверхности Земли- Радиолокационная станция бокового обзора (РЛС БО) сканирует поверхность Земли с помощью радара, расположенного на самолете, летящем вдоль границы некоторой зоны обзора по заданной траектории. Одним из режимов работы РЛС является
определение положения объектов, расположенных, на дорогах в зоне обзора. При сканировании необходимо учитывать то обстоятельство, что элементы ландшафта, непроницаемые или плохо проницаемые для радиоволн, могут заслонить часть дорог, в результате чего, некоторые объекты будут пропущены. К таким элементам ландшафта можно отнести рельеф и лесные массивы. При этом возникают следующие задачи:
необходимо определить, какие участки дорог будут видимы при заданном положении самолёта;
необходимо определить, с каких точек траектории самолёта будут видимы определенные участки дорог;
необходимо определить, какие участки дорог будут невидимы с любой точки траектории самолёта;
Особенности поставленных задач таковы, что необходимы десятки и сотни тысяч полигонов заслонок для достаточно точной аппроксимации карты местности, а определять видимость необходимо быстро. Если последние две задачи можно решить на этапе планирования сканирования местности, то первую, необходимо решать в реальном времени, чтобы в каждый момент знать, какие участки местности можно сканировать при текущем положении самолёта, а какие сканировать бесполезно.
Для решения задачи видимости в наиболее общем виде, а именно, между площадками-полигонами в пространстве, существует несколько известных алгоритмов - портальный [39] и комплекс видимости [49,86], но время их работы сильно зависит от количества заслонок. Верхние оценки времени составляют 0(№) для портального метода и 0(N logN) для комплекса видимости, где N - количество заслонок. Это делает практически невозможным решение поставленных задач не только в реальном времени, но и вообще за приемлемое время. Даже при относительно небольшом количестве заслонок в 5000 единиц количество операций составит 1015 (для комплекса видимости) что на современных процессорах, выполняющих миллиард операций в секунду,
займет 10 секунд, то есть около 12 суток непрерывных расчетов- Дело е том, что существующие методы разрабатывались для определённых задач и условий, и одним из таких условий является то, что объекты значительно чаще являются невидимыми, чем видимыми. В качестве примера, можно привести этаж здания, котда из каждой комнаты видимы лишь несколько соседних комнат, а все остальные - невидимы. Существующие методы используют это обстоятельство, что позволяет им значительно сократить время расчётов. В случае с ландшафтом (открытым пространством), невидима лишь малая часть объектов, а большинство - видимы, поэтому время работы существующих методов приближается к верхним оценкам.
Достичь более высокой скорости расчетов можно двумя способами. Во-первых, с помощью увеличения скорости вычислений, повышая быстродействие вычислительной системы и оптимизируя программу. Во-вторых, с помощью более эффективных методов решения. Если с помощью первого способа можно увеличить быстродействие лишь в несколько раз, то более эффективный метод позволит достичь увеличения скорости вычислений на несколько порядков. Например, если удастся снизить степень зависимости времени вычислений от количества заслонок хотя бы на единицу.
Таким образом, требуется метод, который позволит решать поставленные задачи более эффективно, чем существующие методы. Главным критерием эффективности является время решения. Как было показано выше, существующие методы анализа видимости для общих случаев требуют больших вычислительных затрат. Задачи видимости для частного случая можно решать более эффективно, чем такие общие задачи анализа. Если ровные участки наблюдаемых дорог аппроксимировать отрезками прямых, то вместо анализа видимости между площадками-полигонами, достаточно определить видимость между двумя отрезками; отрезком дороги и отрезком траектории самолета.
Кроме метода решения задачи видимости, требуется разработать способ представления данных о ландшафте, который позволит отсеивать заслонки, не влияющие на видимость между заданной парой площадок. Как правило, на видимость между двумя площадками влияет лишь некоторая часть заслонок. Определив, какие заслонки не влияют на видимость, можно значительно увеличить скорость решения задачи видимости, так как время её решения зависит от числа заслонок. Простой способ отсеять лишние заслонки - их последовательный перебор и проверка того, влияют они на видимость, или нет. Этот способ требует времени, пропорционального количеству заслонок. Так как количество заслонок, которыми представлен ландшафт велико, то требуется более эффективный метод, позволяющий отсеивать сразу группы заслонок, не проверяя каждую из них.
Цели исследования.
Как отмечалось выше, существующие методы решения задачи видимости требуют большого времени и не подходят для решения задач, возникающих при сканировании поверхности Земли. Поэтому целью данной работы является разработка метода и построение на его основе алгоритма для быстрого решения задачи видимости между площадками-отрезками для ландшафтов, аппроксимированных полигонами.
Научная новизна.
- Разработан новый метод решения задачи видимости на плоскости и в трёхмерном пространстве, позволяющий получить полное непрерывное множество возможных отрезков видимости между площадками-отрезками. Время его работы значительно меньше зависит от количества заслонок в сцене, чем у существующих методов, оно составляет 0(N2logN}? тогда как для лучшего из существующих методов, комплекса видимости, 0(N logN),
где N - количество заслонок. Это позволяет использовать разработанный метод для расчёта видимости при большом количестве заслонок;
На основе нового метода разработан алгоритм для решения задачи видимости между двумя отрезками в пространстве;
Разработан способ хранения данных цифровой карты местности и алгоритм для выборки из нее заслонок на определенном участке карты- Способ основан на использовании тетрарного дерева. В данной работе рассмотрены особенности его применения для решения задачи видимости.
Практическая ценность.
Разработана программа расчета видимости участков дорог с траектории самолета-носителя РЛС бокового обзора.
Публикации.
По результатам исследований опубликовано 8 печатных работ.
На защиту выносятся.
Разработанный метод решения задачи видимости между отрезками в пространстве, позволяющий получить полное непрерывное множество возможных отрезков видимости между площадками за время 0(N2logN);
Разработанный способ хранения данных цифровой карты местности и алгоритм для эффективной выборки из нее заслонок на определенном участке карты.
Структура и объем диссертации.
Диссертация состоит из введения, четырёх глав, заключения, списка использованной литературы (105 наименований), приложения и изложена на 128 страницах машинописного текста, содержит 3 таблицы и 69 рисунков. Приложение к диссертации представлено на 2-х страницах,
во введении сформулирована задача, показана актуальность темы диссертации, научная новизна предложенных методов и их практическая ценность.
в первой главе описаны условия, при которых необходимо определять видимость при сканировании поверхности Земли с помощью РЛС БО, проведён анализ существующих методов и алгоритмов решения задачи видимости, сделана оценка их эффективности для решения задачи видимости возникающей при сканировании земной поверхности,
во второй главе предложен и рассмотрен новый метод решения задачи видимости, в котором решение происходит не в объектном пространстве (пространстве, в котором находятся площадки и заслонки), а в пространстве возможных отрезков видимости.
в третьей главе рассмотрены разработанные структуры данных и алгоритмы, которые позволяют компактно хранить информацию о ландшафте и быстро формировать данные о заслонках, необходимые для решения задачи видимости,
в четвертой главе дано краткое описание пакета программ расчета видимости участков дорог и траектории самолета-носителя РЛС БО, приведены его результаты его работы, исследованы характеристики нового метода решения задачи видимости. Для сравнения рассмотрены показатели еще двух существующих методов определения видимости.
в заключении сделаны выводы и даны рекомендации по применению разработанного метода и алгоритмов для решения задачи видимости.
Радиолокационные системы бокового обзора
Получение точной и оперативной информации о земной поверхности необходимо во многих областях человеческой деятельности. Это могут быть как военные области, например, разведка, так и гражданские -картографирование, экологический мониторинг [3]. Одним из способов исследования земной поверхности является радиолокационное сканирование, В этом разделе рассмотрены основные принципы, использующиеся при радиолокационном сканировании, и приведены некоторые параметры современных радиолокационных систем.
Радиолокационная сканирующая система излучает радиоволны, концентрируя их в определенном направлении с помощью антенны, и принимает отраженный сигнал с заданного направления. Основной поток излучаемых и принимаемых волн концентрируется в одном направлении, определяемом диаграммой направленности антенны [7,17]. Наряду с антеннами, имеющими постоянное направление концентрации потока, существуют антенны, допускающие электронное управление этим направлением. Такие антенны называются фазированными антенными решётками (ФАР) [5]. Максимальный угол, на который можно повернуть луч ФАР достигает 60, Для повышения дальности сканирования, сканирующую систему обычно располагают на летательном аппарате, это может быть самолёт, вертолёт, аэростат или спутник. Сканирующие системы разделяются в зависимости от метода сканирования на системы кругового и бокового обзора.
В системах кругового обзора сканирование происходит путём вращения антенны вокруг вертикальной оси (см. рис. 1.1а), что позволяет получить плоское изображение [10]. Антенна РЛС кругового обзора имеет узкую диаграмму направленности в горизонтальной (азимутальной) плоскости и достаточно широкую в вертикальной (угломестной) плоскости. Линейная разрешающая способность систем кругового обзора зависит от расстояния до ооыжти. При шир и цс луча в Г_ коюрую ожтсчпвжп современные антетпш, ;ин объектов на риееншпш 1 МО км разрешение составляет около полугора кнломеїров. Шма июль ниткой разрешающей епоеобноетп RilC кругового обзора нашли ограниченное применение в задачах сканирования темной поверхности, и применяются и основном для сложения за воздушными целями. В системах бокового об юра антенна радара устанавливается неподвижно вдоль фюзеляжа сауолста-иоешоля, а сё длина увеличишься до рюмерой, разрешающей способности в горігкштальпой плоскости, При прямолинейное! полёте ушйґл диаграмма направленности антенны формируется в направлении, перпендикулярном траектории движения самолёта (см. рис. 1.16). h о позволяет осуществлять ошор местное в некоторой полосе, ширина которой определяется дальностью действия VJIC.
Современные системы бокового обзора иеполплутот метод искусегвеннош ржтфьта антенны [14]. Суншость метола чаключасгся в тлулешш РЛО когерешиых тондирук)ош& сигналов при движении вдоль прямолинейной траектории полёта поеитхлш, их запоминании и когерентном
сложении. При этом размер антенны как бы увеличивается до длины участка траектории самолета, на котором происходит сложение сигналов. Эта длина зависит от возможностей запоминания отражённых сигналов и значительно превышает размеры фюзеляжа самолёта. Из-за существенного увеличения размеров антенны РЛС бокового обзора с искусственным раскрывом антенны позволяют добиться существенного повышения разрешающей способности (порядка метров), независимой от дальности наблюдения и длины волны зондирующего сигнала.
Например, подобный метод используется в комплексе авиационного дистанционного зондирования, размещенном на самолете Ил-20М. Он позволяет производить обзор и картографирование земной поверхности с разрешением порядка 15 м при ширине полосы до 100 км [104].
Высокая разрешающая способность позволяет эффективно применять РЛС бокового обзора для картографирования земной поверхности и выделения малоразмерных целей на ней. В особый класс задач обычно выносится определение положения движущихся по поверхности или над поверхностью объектов. Выделение движущихся объектов происходит за счёт использования допплеровского эффекта, при котором частота сигнала, отраженного от движущегося объекта, отличается от частоты зондирующего сигнала. Это позволяет легко различать отражения от движущихся объектов и отражения от неподвижной земной поверхности.
РЛС бокового обзора может работать в различных режимах обзора, которые можно свести к трём основным типам - передне-боковой обзор, телескопический обзор и секторный обзор.
При передне-боковом обзоре возможна ориентация луча как перпендикулярно (см, рис. 1.2а), так и под некоторым углом к направлению движения самолёта (см. рис. 1.26). Во втором случае несколько сужается полоса обзора, но появляется возможность обнаруживать объекты с упреждением. Для работы в таком режиме антенна разворачивается механически, лийо используется электронное управление направлением jy m ФАР. Дальнейшего увеличения разрешающей способности РЛС БО можно добиться и режиме гедеешпшіеекош обзора, Б лщм случае применяются мподы іимш рафии, киї да один и ют же чаешк поверхности ПОСТОЯНЕН) сканируется е ртличиых точек іраезсшрии [105] с различных углов. Размер сканируемого участка определяется шириной луча РЛС. В тгом случае луч радара постоянно меняет ориентацию (см. рис. 1.2п). (векторный об-зор пеполь-зуетея для быстрою получения информации о достаточно большом участке поверхности. При этом ось зондирующего луча поворачивается соішссі но с ноетунагелыплм движением самолета (см. рис. ] .2г) и изображение получается в виде секюра
Видимость точка-отрезок
Вели отрезок пересекает хотя бы одну из заслонок, между точечными площадками нег видимости. Нижняя оценка времени работы алгоритма - Q(l), таким будет время в случае, когда отрезок пересекает первую же проверяемую заслонку. В худшем случае, когда пересечения нет, придется перебрать все заслонки, поэтому верхняя оценка времени решения этой задачи - 0(N)7 где N - количество заслонок. Количество перебираемых заслонок можно уменьшить, если воспользоваться пространственной когерентностью [18]. Например, можно построить некоторую иерархию описанных вокруг заслонок тел, и проверять пересечение отрезка сначала с этими телами. Можно построить дерево разбиения объектного пространства и проверять отрезок по нему. Это может быть, например, двоичное [74], тетрарное или восьмеричное дерево [33,34,35]. В этом случае среднее время решения задачи удастся существенно снизить.
Пространство отрезков видимости, когда обе площадки - точки, является нуль-мерным и состоит из единственного отрезка- Каждая заслонка отображается в это пространство как наличие точки, когда отрезок пересекает заслонку, или ее отсутствие, когда пересечения нет. Можно показать, что ни скорость работы алгоритма, ни размерность пространства отрезков видимости не зависят от размерности объектного пространства, для которого ищется решение задачи видимости. Можно перенести этот алгоритм как в трехмерное пространство, только здесь в качестве заслонок будут выступать не отрезки, а полигоны, так и в пространства большей размерности. При этом увеличатся лишь константы при оценках времени, но не сами оценки.
В случае, когда одна из площадок является точкой, а другая - отрезком, задача решается методом точечного проецирования заслонок (Z\) с площадки-чочки (Р,) на площадку-отрезок (Рз,Ь2) (рис. 23}. Проекции заслонок (SO можно рассматривать как их тени, отбрасываемые точечным источником света, расположенным на площадке-точке, на площадку-отрезок. Если проекции заслонок полностью закрывают площадку-отрезок, видимости между площадками нет. Нижняя оценка времени работы алгоритма останется такой же, как и в предыдущем случае, Q(l). Таким будет время в случае, когда тень от первой же проверяемой заслонки полностью закрывает отрезок. Очевидно, что если для решения перебираются все заслонки, то при любой размерности задачи видимости заслонка, которая полностью заслоняет одну площадку от другой, может быть выбрана первой. Поэтому нижняя оценка времени останется равной Q(l) для задачи видимости любой размерности. В худшем случае нужно будет перебрать все заслонки, что потребует 0(N) времени. Кроме того, может оказаться, что ни одна из заслонок не заслоняет площадку полностью, но тени от нескольких заслонок в совокупности покрывают ее всю. Для определения таких случаев необходимо найти объединение всех теней. Это можно сделать с помощью сортировки и последующего обхода отрезков тени. Сортировка требует времени O(NlogN) [8], поэтому общая верхняя оценка времени работы алгоритма - O(NlogN).
Точка и отрезок в качестве площадок Пространство отрезков видимости в этом случае одномерное и состоит из всех отрезков, которые можно провести между площадкой-точкой и площадкой-отрезком. Фактически, это отрезок [0,1] одномерной прямой (см. рис. 2.4), точки заслонок переходят в пространство отрезков видимости как точки (М IVT), а заслонки - как отрезки (MN = M N ). Координата точки в пространстве отрезков видимости фактически является параметром t в уравнении, задающем площадку-отрезок.
Хранение информации о карте местности
Для рассмотренного в предыдущей главе метода решения задачи видимости необходима информация о заслонках. Эта информация берётся из цифровой карты местности. Цифровая карта местности в зоне обзора, сканирование которой требуется произвести, известна заранее. На этой карте обозначены все дороги, лесные массивы и параметры рельефа. В данной главе описан алгоритм формирования заслонок по карте местности и структура их хранения. Такая структура позволяет выбирать заслонки, необходимые для решения отдельной задачи видимости, не перебирая все заслонки, что сокращает время решения.
Для работы с участками земной поверхности наиболее эффективно использовать иерархическое представление данных [37,38,41,42,43,44,45,66,87,88,92]. Такой формат хранения позволяет быстро выбирать нужные полигоны, не перебирая все полигоны, а также работать с разным уровнем детализации рельефа. Уровни детализации обычно используются при визуализации ландшафтов, когда дальние от наблюдателя участки рисуются с меньшим количеством полигонов, чем ближние. Для рассматриваемых задач различные уровни детализации используются для предварительных, оценочных расчетов видимости. При малой детализации рельефа заслонок будет меньше, и время расчётов значительно сокращается. Исходные данные о карте зоны обзора представлены в виде плоского изображения (см. рис. 3-І), Дороги заданы набором точек, определяющим ломаные, кроме того, каждая дорога характеризуется некоторой шириной. Лесные массивы ограничены замкнутыми контурами, каждый массив имеет определенную высоту деревьев. Рельеф определяется картой высот: двумерным массивом высот для точек карты, расположенных в узлах сетки, наложенной на карту местности. Размер карты равен 100x150 км, точки дорог и контуров лесных массивов заданы с точностью 10 м, шаг сетки карты высот - 1 00 м.
Перед расчетом видимости карта преобразуется в формат, который позволяет эффективно находить полигоны заслонок. Преобразование включает в себя следующие этапы; - контуры лесных массивов разбиваются на выпуклые многоугольники; - из этих многоугольников вырезаются участки, соответствующие дорогам; - карта высот преобразуется в тетрарное дерево [1,12]; - для многоугольников лесных массивов и участков дорог определяется, в какие ячейки тетрарного дерева они попадают; Разбиение на выпуклые многоугольники контуров лесных массивов необходимо для более эффективной работы алгоритмов отсечения многоугольников прямой [11]. Отсечение используется при вырезании пространства дорог из лесных массивов, для определения попадания лесного массива в ячейку тетрарного дерева и для нахождения трехмерных полигонов,, соответствующих лесным массивам. При отсечении произвольного многоугольника (см, рис. 3.2) может образоваться несколько точек пересечения, при этом нужно соединить их в правильном порядке, чтобы получить корректный результат.
Если многоугольник выпуклый (см. рис. 3.3) - алгоритм отсечении значительно упрощается, точек пересечения может быть ровно две. Для получения отсеченного многоугольника достаточно обойти все вершины, и выбрать те из них, которые лежат с нужной стороны от прямой или принадлежат ей. Если две последовательные вершины лежат с разных сторон от прямой, значит соответствующее им ребро пересекает прямую и в результирующий полигон следует занести точку пересечения. Очевидно, что выпуклых полигомон будет больше, чем произвольных начальных, ни более эффективные алгоритмы работы с ними окупают эго. Кроме того, с выпуклым многоугольником можно эффективно производить и другие операции, кроме отсечения. Например, проверку на пересечение с прямоугольником, которая часто используется при работе с тетрарным деревом.
Вырезание областей, соответствующих дорогам, необходимо из-за того, что в контурах лесных массивов они не были учтены, то есть лесной массив полностью покрывает внутреннее пространство контура, включая дороги, проходящие внутри него (см. рис. 3.4). Очевидно, что если не произвести вырезание окрестностей дорог, то все такие лесные дороги будут всегда заслонены полигонами лесного массива.
Характеристики программы расчета видимости
Программный пакет состоит из 3-х программ, объединенных для удобства в единый исполняемый модуль. Первая программа предназначена для преобразования цифровой карты местности в тетрарное дерево (см. главу 3). Она считывает данные о положении дорог, лесных массивов и данные о карте высот из файлов, вырезает окрестности дорог из лесных массивов и формирует тетрарное дерево- Эта же программа формирует заслонки для некоторого района карты, которые затем используются для решения задачи видимости. Программа построения тетрарного дерева выполняется один раз при запуске пакета, а далее используется только подпрограмма выборки из него заслонок. Вторая программа предназначена для определения видимости между отрезками в пространстве с помощью вышеописанного метода (см. главу 2). Третья программа позволяет вывести зону обзора на экран. Это может быть как вид сверху, так и ее перспективная проекция. Пользователь может выбрать наиболее подходящий вид и точку наблюдения, в случае перспективной проекции.
Программный пакет выполнен на языке C++ для операционной системы Microsoft Windows 95 и более поздних версий. Он использует дополнительную библиотеку MFC для создания интерфейса и библиотеку DirectX 7.0 для отображения перспективной проекции зоны обзора [15,16]. Кроме того, программе отображения перспективной проекции требуется графический акселератор, если он отсутствует, карта зоны обзора отображается только в виде сверху. Программный пакет имеет удобный пользовательский интерфейс, основанный на меню и наборе диалогов.
Программный пакет протестирован на цифровой карте местности с количеством прямолинейных отрезков дорог около 3000 и количеством отрезков в ломаных, ограничивающих лесные массивы, около 100. Тестирование проводилось на компьютере с процессором Intel Celeron 433 MHz с 128 Мб памяти и графическим акселератором Nvidia Riva TNT2.
Время работы программы построения тетрарного дерева составляет около 2-х секунд. Время построения перспективной проекции зоны обзора варьируется в зависимости от положения и направления камеры от 0.025 до 0.2 секунд, то есть от 5 до 40 кадров в секунду. Временные показатели расчета видимости в различных режимах приведены в таблице 4.1.
Режимы работы тестировались на нескольких вариантах постановки задачи. Во-первых, вычисления проводились либо для всей зоны обзора, либо для некоторого ее участка. Во-вторых, режимы дополнительно тестировались на карте без учета рельефа, в этом случае количество заслонок и отрезков дорог несколько меньше іак кт оіш не делятся по границам ЗІЧССК. m т&олицы видно, чт нрешз решения наиболее сильно зависит от количества дорог, тк происходит run ому, ьп-о для каждой дороги приводится решать спою -задачу видимости. 1 акт сйоііство позволяем хорошо распараллеливать алгоритм решения, так как фактически нужно решать множество петавиеимык шд-ін.
Ретультаты работы программ шжатаны на рисунках 4J-4.9. На иереиектшшон проекции сканируемой зоны (см, рис, 4Л) серым цветом обозначено поверхность Земли п тоне ойчора, зеленым лесные массивы. Такой режим позволяет отображать карту местности в привычном для человека виде.
