Диссертация (1137226), страница 10
Текст из файла (страница 10)
Основная идея алгоритма построения оверлеев многоугольников с помощью триангуляции заключается в построении совместной триангуляции исходных многоугольников (при которой структурными линиями служат стороны обоих операндов), а затем выбора из множества полученных треугольников некоторых, согласно выполняемойоперации и принадлежности каждого из треугольников исходным множествамоперандам [70]. Избранные треугольники можно объединить в многоугольники,хотя для рассматриваемой задачи это не обязательно.Алгоритм Леонова (Грейнера-Хормана) состоит в поиске и маркировкевсех пар пересекающихся рёбер контуров, после чего проводится трассировка,начинающаяся с любой вершины одного из контуров, выделяющая все мини60мальные ограничивающие контуры областей, полученных наложением операндов.
Каждый из контуров маркируется согласно выполняемой операции и принадлежности операндам, после чего проводится сборка этих контуров в результирующее множество [70].Алгоритм Ватти также называется скан-линейным. Его основная идея состоит в том, что все вершины операндов упорядочиваются по значению их ординат, и каждая из них порождает горизонтальную скан-линию.
Далее припоследовательном просмотре скан-линий производится анализ их пересеченийс точками и рёбрами операндов, поддерживается список контуров, в которыйвносятся изменения, соответствующие характеру и последовательности пересечения очередной скан-линии с вершинами и сторонами [78].Эти известные алгоритмы имеют программные реализации, которые были использованы для исследования. Для построения триангуляции и для выполнения операций над треугольниками применена библиотека ComputationalGeometry Algorithms Library [86].
Алгоритм Леонова взят из [118]. За основуреализации алгоритма Ватти взят код [123].Для первого этапа тестов использованы данные о природных пожарах, полученные в2011году, состоящие из3906векторных файлов. Каждый файлсодержит от одного до нескольких тысяч полигонов простой формы, как правило — четырёхугольной, являющихся векторным представлением пикселей растрового изображения, на которых детектирован пожар, типичный вид фрагментаодного операнда приведен на рисунке 2.9.Файлы были разбиты на группы по месяцам. Для тестов алгоритмов напервом этапе использована подгруппа файлов, имеющих общий размер 100 килобайт. Также была сформирована группа, включающая в себя все файлы всехмесяцев.
В таблице 2.3 приводятся характеристики этих групп. Тесты всех трёхалгоритмов проводились только для «Подгруппы», результаты представлены втаблице 2.4.Имеющаяся реализация алгоритма Леонова не прошла по временным огра61Рисунок 2.9 – Фрагмент одного векторного файла.Таблица 2.3 – Характеристики тестовых групп файловМесяцАпрельМайИюньИюльСентябрьОктябрьПодгруппаВсе месяцыЧислофайОбщийловмер4701231132239726821883906МБ3,111,211,62,21,81,50,131,1разфайлов,ОбщеечислоОбщееконтуроввершин2063469560622921619313298893860819091510238940541647280464772531923575238991134325числоничениям, кроме того, в этой реализации при вычислениях производится перевод координат из чисел с плавающей точкой в целочисленные 64-битные значения и обратно.
По этой причине координаты точек не сохраняются строго, чтоможет вызвать проблемы при дальнейшей обработке. По этим причинам былопринято решение отказаться от алгоритма Леонова.Недостатком триангуляционного алгоритма оказалось то, что при объединении многих наложенных контуров количество треугольников растёт квадратично от числа объединений. Таким образом, на реальных данных, содержащихобласти с многократным перекрытием, число треугольников резко возрастает,а сами они уменьшаются до ничтожных площадей.
Реальные данные, которыетребуется обрабатывать в данной задаче, могут содержать многократное наложение полигонов, так как один и тот же пожар может быть детектировандесятки раз на различных пролётах КА. На рисунке 2.10 приводится примеробъединения двух прямоугольных контуров (каждый из которых может быть62Таблица 2.4 – Результаты обработки тестовой подгруппы тремя выбранными алгоритмамиАлгоритмТриангуляцияЛеоноваИюньВремя, сЧисло0,0380,110,017ров1314596598контуЧисловершин394238803883представлен как два треугольника), в результате которого при использованииметода триангуляции получается 10 треугольников, и объединение трёх контуров, в результате которого получается уже 31 треугольник.Рисунок 2.10 – 2 контура, 10 треугольников (слева), 3 контура, 31 треугольник (справа).Обратное объединение треугольников в некоторую фигуру само по себеявляется трудной задачей, требующей существенной доработки алгоритма триангуляции.
По этой причине было принято решение отказаться от метода триангуляции.Алгоритм Ватти оказался наиболее перспективным для решения поставленной задачи, однако использованная его реализация потребовала существенных доработок: исключена рекурсия при перемещении по спискам (деревьям)вершин, активных рёбер, фигур; исключено задание в явном виде таблицы попарных пересечений многогранников; учтена возможность пересечения фигур,находящихся в одном файле. Опишем каждую из этих доработок более подробно.2.5.4. Доработки реализации алгоритма ВаттиИсключение рекурсии.Алгоритм Ватти оперирует с несколькими списками объектов, это список вершин (составляется из вершин исходных фигур,пополняется в процессе работы пересечениями рёбер), список активных рёбер,63списки активных фигур и построенных фигур. В версии [123] эти списки реализованы как бинарные деревья, для оптимизации поиска.
Однако, перемещениепо спискам в оригинальном коде было реализовано в виде рекурсивного вызовафункций обработки элемента. При работе с большими объёмами данных степени самых удалённых от корня вершин деревьев возрастают до несколькихдесятков тысяч. При использовании рекурсивных вызовов для перемещения подереву это означает вызов функции самой из себя несколько десятков тысячраз. По этой причине при обработке больших групп файлов (например «Май»и «Июнь») происходило исчерпание стека вызовов и аварийное завершение алгоритма и самой программы. Были сделаны доработки с целью исключить рекурсию.
В переработанной версии алгоритма глубина вызовов функций не превышает5,рекурсия исключена.Таблица попарных пересечений.В исходной версии алгоритма дляминимизации вычислений алгоритма применён простой метод уменьшения количества контуров, для которых используется скан-линейный метод.
Идея заключается в том, что каждый из операндов представлен множеством отдельныхконтуров: ∈ =⋃︀=1 и=⋃︀=1 , но при этом далеко не каждый контурпересекает хотя бы один контур ∈ и наоборот. Таким образом,каждый операнд можно разбить на два подмножества, активное и пассивное: = + , = + (2.29)Пассивные части операндов исключаются из выполнения скан-линейнойпроцедуры и могут быть добавлены уже потом к результату: ∩ = ∩ ;(2.30) ∖ = ∖ + ;(2.31) ∪ = ∪ + + .(2.32)64Однако, реализация этого подхода выполнена с расчётом на небольшое количество контуров. В частности, для получения списков пассивных и активныхконтуров используется массив чисел, имеющий размер, равный произведениючисла контуров двух операндов.
Для решаемых в рамках проекта задач оба этичисла могут превышать100000,что приводит к невозможности размещения воперативной памяти такого массива. Была произведена доработка алгоритма, врезультате которой необходимый размер массива стал равен не произведению,а сумме числа контуров в операндах.Пересечение фигур в одном операнде.Исследованная реализацияалгоритма Ватти не рассчитана на то, что контуры, принадлежащие одномуоперанду могут пересекаться. В случае, если это происходит, при подсчёте пересечений скан-линии с контурами операнда алгоритм исключает их пересечениеиз результата, пример приведен на рисунке 2.11.Рисунок 2.11 – Пример неверного объединения пересекающихся полигонов.Была сделана надстройка над алгоритмом. Каждый из операндов предварительно разбивался на группы контуров (слои), такие, что внутри каждогослоя контуры не пересекались:=∑︁=1() : ∀ : , ∈ () → ∩ = ∅.(2.33)65Для разбиения на слои разработан специальный алгоритм, использующийпроецирование ограничивающих прямоугольников фигур на вспомогательныйрастр.
Схема работы алгоритма представлена на рисунке 2.12. В результатеисполнения алгоритма получается несколько слоёв, в каждом из которых содержатся взаимно непересекающиеся контуры. Как правило, слои с большимпорядковым номером содержат меньшее количество контуров, поэтому слоиобъединяются начиная с меньших номеров с целью уменьшения количества вычислений алгоритмом Ватти.Рисунок 2.12 – Блок-схема алгоритма разбиения на слои.662.5.5. Исследование доработанного алгоритма путём численногоэкспериментаРезультаты тестов алгоритма на множествах таблицы 2.3 приведены в таблице 2.5. Проводилась операция объединения всех контуров всех файлов в группе в один набор контуров.Таблица 2.5 – Результат работы доработанного алгоритма на реальных данных.ГруппаВремя, сЧисло слоёвЧислоровАпрельМайИюньИюльСентябрьОктябрьВсе месяцы68714374475143134168926638419таконтурезульта12495231033135364626754539478234Числошинверрезультата917832565683218994552341970303447301282.5.6.
ВыводыИсследованы существующие алгоритмы, решающие задачу построения объединения, пересечения и разности наборов многоугольников. Из всех алгоритмов выбран наиболее пригодный для решения поставленной задачи, и произведена его доработка для эффективного функционирования в условиях большогоколичества пересекающихся полигонов простой формы. Сделана надстройканад алгоритмом, позволяющая обойти один из его принципиальных недостатков, некорректную обработку операндов со взаимно пересекающимися контурами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
