A review of the algorithms of polygon overlays design.pdf Во многих приложениях вычислительной геометрии икомпьютерной графики, в системах автоматизированного про-ектирования (САПР), в геоинформационных системах (ГИС), вразличных векторных графических редакторах основные объ-екты описываются с помощью плоских многоугольников.Одной из основных операций над многоугольникамиявляется операция построения оверлеев (объединения, пе-ресечения или разности).Несмотря на внешнюю простоту постановки, многиесуществующие алгоритмы её решения обладают сущест-венными недостатками для использования на практике. Ос-новная проблема связана с потерей вычислительной точно-сти при вычислениях, что приводит к некорректной работеалгоритмов. Во многих алгоритмах устранение такого родапроблем с точностью приводит к существенному усложне-нию реализации алгоритма, что не всегда отражается в ори-гинальных работах авторов.С другой стороны, существует ряд алгоритмов, которыев настоящее время широко не известны по ряду причин: ли-бо из-за того, что они напечатаны в недоступных источни-ках, либо они не опубликованы вообще. Такая ситуациясложилась с некоторыми алгоритмами, на основе которыхразработаны некоторые общедоступные библиотеки про-грамм построения оверлеев. Такие библиотеки доступны винтернете, доступны их общие описания, однако зачастуюнаучных статей с описанием принципов работы алгоритмови их сравнения с аналогами нет.В настоящей работе предпринята попытка обобщениярезультатов исследований различных алгоритмов построе-ния оверлеев.ПОСТАНОВКА ЗАДАЧИРассмотрим евклидово пространство размерности 2 справой декартовой системой координат. Будем считать,что многоугольники, подающиеся на вход алгоритмовпостроения оверлеев, расположены в этой плоскости.Определение. Ребром называется направленныйотрезок с началом в точке а и концом в точке b, несовпадающей с а, который обозначается как E(a,b) .При этом будем говорить, что для точки b ребро Е яв-ляется входящим, а для точки а - выходящим.Определение. Контуром называется множестворебер {E0,E1,...,En-1} такое, что n > 2 и i {0,...,n−1}:Ei−1=E(vi−1,vi),Ei=E(vi,vi+1). Точка vi , для которойребра Ei−1 и Ei являются соответственно входящим ивыходящим, будем называть i-й вершиной контура С,ребра Ei−1 и Ei - соседними или смежными. Порядокобхода ребер контура C = {E0,E1,...,En-1} c увеличени-ем индекса ii+1 будем называть прямым направ-лением обхода, а противоположный ему - обратным.Заметим, что одной точке плоскости может соответ-ствовать несколько вершин контура, такие вершиныбудем называть кратными.Определение. Областью называется ограничен-ное полигональное открытое связное множество наевклидовой плоскости, определенное с точностью домножества меры нуль. Под полигональностью пони-мается то, что граница области состоит из замкнутыхломаных.Рассмотрим границу dA некоторой области А. Еслиориентация dA согласована с ориентацией А, мы при-ходим к соответствию между границей области и на-бором контуров на плоскости. Для того, чтобы онобыло взаимно-однозначным, добавим к традиционно-му определению два ограничения. Итак, рассмотрим,контур C, содержащий n ребер.Определение. Контур С называется ограничиваю-щим контуром области А, если выполняются следую-щие условия:1) С  dA ;2) обход С в прямом направлении является поло-жительным обходом, т.е. обходом, при котором об-ласть A остается слева;3) i{0,...,n−1} : ƒ>0 :xƒ+ (ƒi) : xA ;4) i{0,...,n−1} : ƒ>0 :xƒ− (ƒi): x∉A .Определение. Общим полигоном или много-угольником называется множество всех ограничи-вающих контуров некоторой области.Внешним контуром области А назовем ограничи-вающий ее контур, положительный обход которогопроизводится против часовой стрелки. Внутреннимконтуром области А назовем ограничивающий ее кон-тур, положительный обход которого производится почасовой стрелке. Очевидно, что в произвольном поли-гоне может быть один и только один внешний контур.Определение. Многоугольник называется выпук-лым, если определяемое им множество точек являетсявыпуклым.Определение. Многоугольник называется про-стым, если он имеет, по крайней мере, две различныхточки, если ни одна пара непоследовательных реберне разделяет точку и если каждая пара последова-тельных ребер разделяет только одну точку.Определение. Многоугольник называется регу-лярным, если он не имеет пересекающихся или «ви-сящих» ребер и совпадающих точек.Определение. Вершинно-полным называется мно-гоугольник, который не имеет пересекающихся ре-бер, однако у него могут быть совпадающие вершиныи коллинеарные ребра.Определение. Ориентированным называется мно-гоугольник, любые два ребра которого либо не пере-секаются, либо коллинеарны, либо пересекаются вточке, являющейся конечной точкой как минимум од-ного из ребер.Указанные классы полигонов формируют следую-щую иерархию: выпуклые  простые  регулярные вершинно-полные  ориентированные  общие.Итак, рассмотрим два двумерных многоугольникаA и В. Под выполнением некоторой булевой операциинад многоугольниками A и В понимается выполнениеоперации над описываемыми ими областями и полу-чение множества многоугольников, описывающегополученную область.Определим следующий набор возможных операций:1. Объединение (рис. 1,a):{( , ) : ( , ) или AB= xy xy A (x,y)B}.2. Пересечение (рис. 1,б):AB={(x,y) : (x,y) Aи (x,y)B}.3. Разность (рис. 1,в):A−B=clos {(x,y) :(x,y) Aи (x,y)∉B}.aABABABбвРис. 1. Набор операций над многоугольниками A и BАЛГОРИТМ САЗЕРЛЕНДА - ХОДЖМАНААлгоритм Сазерленда - Ходжмана является однимиз самых первых и простых алгоритмов отсечениямногоугольников [8]. Он был базовым алгоритмомдля процессора Кларка [9], который был предтечейалгоритмов, заложенных в классических программахпервых компьютеров Silicon Graphics Inc. Этот алго-ритм рассекает исходный общий многоугольник лю-бым выпуклым многоугольником. Отсекающий мно-гоугольник обычно называют отсекающим окном.Суть алгоритма заключается в том, что отсекаемыймногоугольник последовательно отсекается каждойграницей отсекающего окна (рис. 2).Рис. 2. Отсечение многоугольника выпуклымотсекателем в алгоритме Сазерленда - Ходжмана Алгоритм обрабатывает пересечение каждого ребраисходного многоугольника с каждым ребром отсекате-ля, сохраняя вершины, находящиеся внутри ребра иточки пересечения ребер. Далее алгоритм повторяется,на вход подаются полученный на предыдущем шагевременный многоугольник и другое ребро отсекателя.Существует четыре случая при обработке возможногопересечения ребра отсекаемого многоугольника и реб-ра отсекателя (допустим, что ребро отсекаемого мно-гоугольника идет от вершины S к вершине P):1. Обе вершины (S и P) ребра отсекаемого много-угольника внутри ребра отсекателя, вершина P добав-ляется в выходной список (рис. 3, а).2. Если вершина S внутри ребра отсекателя, а вер-шина P снаружи его, то в выходной список заноситсяточка пересечения i (рис. 3, б).3. Если обе точки (S и P) ребра снаружи ребра от-секателя, тогда в выходной список не попадает ничего(рис. 3, в).4. Если вершина P внутри ребра отсекателя, авершина S снаружи его, то в выходной список зано-сится точка пересечения i и вершина P (рис. 3, г).SВнутри СнаружиPРебро отсекателяaSВнутри СнаружиPРебро отсекателябiSВнутри СнаружиPРебро отсекателявВнутри СнаружиPРебро отсекателягiРис. 3. Варианты пересечения ребра исходногомногоугольника и ребра отсекателя в алгоритмеСазерленда - ХоджманаВ завершении работы алгоритма необходимо рас-смотреть первую вершину и последнее ребро отсе-каемого многоугольника. Если первая вершина нахо-дится внутри текущего ребра, мы сохраняем ее в спи-ске вершин временного выходного многоугольника,иначе мы отбрасываем ее. Что касается последнегоребра, следует заметить, что если в нашем выходномвременном многоугольнике пусто, то весь исходныймногоугольник не должен быть виден в отсекающеммногоугольнике, т.е. мы можем прервать работу. Вином случае, если последнее ребро отсекаемого мно-гоугольника пересекается с ребром отсекателя, тоточка пересечения должна быть добавлена во времен-ный выходной многоугольник.К «плюсам» алгоритма стоит отнести его просто-ту, малую требовательность к памяти (всего два спи-ска цепочек), к «минусам» - довольно высокую тру-доемкость (O (n1n2 log n2)), пригодность только длявыпуклых отсекателей, невозможность обобщениядля построения объединения и разности многоуголь-ников. Кроме этого, к недостаткам алгоритма можноотнести и то, что в результате могут образоваться вы-рожденные многоугольники, когда некоторые рёбрамогут налагаться друг на друга, образуя «перешейки»нулевой ширины.АЛГОРИТМ O'РУРКАОдин из наиболее простых и элегантных алгорит-мов пересечения выпуклых многоугольников былпредложен О'Рурком [11]. Он базируется на болеепростом и грубом методе, описанном в [1].Основная идея алгоритма О'Рурка состоит в сле-дующем. Допустим, даны два выпуклых многоуголь-ника P с L вершинами и Q с M вершинами. Предпо-ложим, что (p1,p2,...,pL) и (q1,q2,...,qM ) - это спискивершин P и Q, упорядоченные при обходе их противчасовой стрелки. Для каждого многоугольника объяв-ляются текущие вершины pi и qi, кроме этого, теку-щие ребра оканчиваются вершинами pi и qi. Идея за-ключается в том, чтобы не двигаться по той границе(P или Q), текущее ребро которой еще может содер-жать необнаруженную точку пересечения. Существу-ет четыре возможных варианта взаимного расположе-ния вершин pi и q j и ребер pi−1pi и qj−1qj (осталь-ные ситуации сводятся к указанным четырем путемзамены ролей P и Q). В одном из этих вариантов(рис. 4, а) мы продвинемся по P, так как текущее реб-ро qj−1qj из Q может содержать необнаруженнуюточку пересечения; по тем же причинам в случае (рис.4, б) мы продвинемся по границе Q.Если все пересечения на текущем ребре из P ужеобнаружены, в то время как текущее ребро из Q всееще может содержать необнаруженное пересечение,мы продвигаемся вдоль P (рис. 4, в); кроме этого,здесь мы должны вычислить точку пересечения реберpi−1pi и qj−1qj . В последнем случае (рис. 4, г) выборпроизволен и можно выбрать, например, Q.i pj qi pj qi j p qi p j qa б в гРис. 4. Варианты взаимного расположения текущихвершин и ребер в алгоритме О'РуркаВ целом, можно сказать, что алгоритм О'Руркаэффективен и прост в реализации, кроме этого, онможет быть легко модифицирован для построенияобъединения и разности многоугольников.АЛГОРИТМ ВЕЙЛЕРА - АЗЕРТОНААлгоритм Вейлера - Азертона [4, 5] является го-раздо более мощным алгоритмом отсечения много-угольников по сравнению с ранее перечисленными.Он пригоден для обработки областей с «дырами» (безсамопересечений) и для любых регулярных отсекате-лей, однако, достигается это ценой заметно большейсложности и меньшей скорости работы.Отсекаемый многоугольник называется объектом(SP), а отсекающий многоугольник - отсекателем(CP). В процессе пересечения не создаются новыеребра, поэтому число выходных многоугольниковминимизировано.Алгоритм описывает SP и СP как циклический спи-сок вершин. Внешние границы многоугольников пред-ставляются упорядоченными по часовой стрелке, авнутренние границы и «дыры» упорядоченными про-тив часовой стрелки. Отсюда, при перемещении посписку вершин, внутренняя область многоугольникадолжна всегда находиться справа. Границы SP или CPмогут пересекаться, а могут не пересекаться. Если онипересекаются, пересечения возникают дважды. Одноиз пересечений происходит, когда ребро SP входитвнутрь CP, а второе, когда выходит. По существу, ал-горитм начинается на «входящем» пересечении и сле-дует по часовой стрелке до внешней границы SP до техпор, пока не будет найдено пересечение с CP. На пере-сечении делается правый поворот и выполняется обходпо часовой стрелке внешней области CP, пока не будетнайдено пересечение с SP. Далее, снова на пересеченииделается правый поворот и выполняется обход по SP.Процесс продолжается до тех пор, пока не будет дос-тигнута стартовая точка. Внутренние границы SP об-ходятся против часовой стрелки.Ниже описаны основные шаги алгоритма:Шаг 1. Нахождение точек пересечения SP и CP -каждое пересечение добавляется в список вершин SPи CP. При этом касания не считаются пересечением,т.е. когда вершина или ребро отсекаемого много-угольника инцидентна или совпадает со стороной от-секателя (рис. 5 и 6). Каждая пересекающаяся верши-на помечается и устанавливается двунаправленнаясвязь между списками SP и CP.a бРис. 5. Случаи, не считающиеся пересечением,в алгоритме Вейлера-АзертонаВходВыходПересечениянетРис. 6. Частный случай пересечения многоугольниковв алгоритме Вейлера - АзертонаШаг 2. Обработка непересекающихся границ мно-гоугольников - вводятся два списка: один для границ,находящихся внутри CP, второй - для находящихсяснаружи. Границы CP, находящиеся снаружи SP, иг-норируются. Границы CP внутри SP формируют «ды-ры» SP. Поэтому копия границ CP идет в оба списка -«внутренний» и «наружный». Границы помещаются всоответствующий список.Шаг 3. Создание двух списков точек пересечений- первый, «входящий» список, содержит только точкипересечения, когда ребро SP входит внутрь CP. Дру-гой, «выходящий» список, содержит точки пересече-ния, когда ребро SP выходит изнутри CP. Тип пересе-чения будет чередоваться вдоль границы. Таким обра-зом, только одно определение необходимо для каж-дой пары пересечений.Шаг 4. Выполнение пересечения. Многоугольникивнутри CP находятся, используя следующую проце-дуру:Шаг 4.1. Точка пересечения удаляется из «входя-щего» списка. Если список пуст, тогда процесс за-вершен.Шаг 4.2. Выполняется обход списка вершин SP,пока не будет найдена точка пересечения. Список SPвплоть до найденной точки копируется во «внутрен-ний» список.Шаг 4.3. Используя ссылку, переходим на списоквершин CP.Шаг 4.4. Выполняется обход списка вершин СP,пока не будет найдена точка пересечения. Список СPвплоть до найденной точки копируется во «внутрен-ний» список.Шаг 4.5. Возвращается обратно на список вершин SP.Шаг 4.6. Повторяем до тех пор, пока не будет дос-тигнута стартовая точка. На этой точке заканчиваетсяновый внутренний многоугольник. Конец алгоритма.Многоугольники снаружи CP находятся, исполь-зуя ту же процедуру, за исключением того, что на-чальная точка пересечения получается из «выходяще-го» списка и список вершин CP обрабатывается в об-ратном направлении. Списки многоугольников копи-руются в «наружный» список.Более подробное описание алгоритма может бытьнайдено в [2, 3].Трудоемкость вычислений пересечений равнаO(n1,n2), где n1 и n2 - соответственно количествовершин SP и CP. При применении методов простран-ственного индексирования рёбер исходных много-угольников, например с помощью R-деревьев, трудо-емкость может быть снижена до O(n1+n2).Такие минусы, как высокая сложность при отра-ботке большого количества особых случаев [2], воз-никающих при реализации, и невысокая скорость ра-боты не позволяютменном списке, а затем помещаются в результирую-щие полигоны. Найти нужный полигон несложно, дляэтого достаточно определить минимальный из внеш-них контуров, содержащих данный внутренний кон-тур. Регион R будет состоять из множества получен-ных таким образом полигонов.Вычислительная трудоемкость алгоритма различа-ется на разных этапах. В среднем она равна1 2 1 2 O((n +n )log(n +n )+n0+zlog(n1+n2)) ,где (n1+n2) - общее число вершин регионов A и В; z- общее число контуров регионов A и В; n0 - макси-мальное число новых вершин.Исходя из вышеперечисленного, можно сделатьвывод, что алгоритм Леонова является одним из луч-ших по важнейшим из параметров (скорости, затра-там на память, численной устойчивости, обработкевырожденных ситуаций).АЛГОРИТМ ШУТТЕАлгоритм Шутте [6] базируется на алгоритме Вейле-ра - Азертона [4], однако имеет несколько ограничений:1. Вершины многоугольников должны быть упо-рядочены по часовой стрелке.2. Многоугольники не должны иметь «дыр».3. Многоугольники не должны быть самопересе-кающимися.Алгоритм состоит из следующих шагов:Шаг 1. Пересечение двух многоугольников. Ре-зультатом являются те же самые многоугольники, содним отличием, что точки пересечения добавляютсякак вершины многоугольников.Шаг 2. Все ребра обоих многоугольников помеча-ются как «внутренние» (ребро находится внутри дру-гого многоугольника), «разделенные» (ребро принад-лежит обоим многоугольникам) и «наружные» (ребронаходится снаружи другого многоугольника).Шаг 3. Находятся минимальные многоугольники.Шаг 4. Все минимальные многоугольники класси-фицируются по трем выходным наборам AB, A\B,A/B. Конец алгоритма.На первом этапе точки пересечения добавляются кспискам вершин многоугольников. Новые вершиныодного многоугольника содержат ссылку на соответст-вующие вершины другого многоугольника. Получив-шиеся многоугольники называются расширенными.Следует заметить, что возможен вариант, когда небудет найдено ни одной точки пересечения. В данномслучае возможна одна из следующих ситуаций:1. Многоугольник А внутри многоугольника В.Здесь любая вершина из А находится внутри В, чтолегко может быть проверено. Если А внутри В, мыпроизвольно разбиваем В на два многоугольника - Абудет находиться где-то на пересечении. Мы делаемразбиение, так как не хотим появления многоуголь-ников с «дырами».2. Многоугольник В находится внутри много-угольника А. Аналогично случаю, описанному выше.3. Многоугольники А и В разделены.Идея, заложенная на втором этапе алгоритма, за-ключается в том, что если одна из вершин ребра со-единена с другим многоугольником, можно прове-рить, располагается ли она внутри или снаружи вто-рого многоугольника. Если ни одна из вершин ребране лежит на ребре второго многоугольника, то дляпроверки, находится ли исходное ребро внутри, мож-но использовать обе вершины.На третьем этапе все ребра обоих расширенныхмногоугольников дублируются в прямые и обратныеребра, которые называются направленными. Разде-ленные ребра дублируются только раз. Для каждогонаправленного ребра мы ищем минимальный, упоря-доченный по часовой стрелке многоугольник, частьюкоторого данное ребро является. Поиск начинается повсем вершинам обоих многоугольников по двум на-правлениям. Повторное добавление одинаковых мно-гоугольников запрещается - каждое ребро включаетсятолько один раз для каждого направления.Для проведения классификации на четвертом эта-пе вводится термин «отцовство». «Отцовство» опре-деляется как отношения между ребрами и исходнымимногоугольниками и между минимальными много-угольниками и исходными многоугольниками. Если«отцовство» доказано, значит объект является частьюисходного многоугольника. Если «отцовство» ложно,значит объект не является частью исходного много-угольника. Кроме значений «доказано» и «ложно»,«отцовство» может быть «неизвестным» и «смешан-ным». «Неизвестное» означает, что убедительныхподтверждений нет. «Смешанное» означает, что су-ществуют противоречащие факты. Это возможнотолько для минимальных многоугольников и означа-ет, что минимальный многоугольник - это «дыра»между двумя исходными многоугольниками.Процесс классификации минимальных много-угольников происходит в два этапа. На первом этапепроверяется «отцовство» каждого минимального мно-гоугольника, после этого решается, к какому классуотносится минимальный многоугольник.Ответ на вопрос, является ли минимальный мно-гоугольник потомком исходного многоугольника,производится при помощи маркировки ребер. Для ка-ждого ребра минимального многоугольника выясня-ется родительский исходный многоугольник.Трудоемкость алгоритма при операциях нахожде-ния пересечений и маркировки ребер равна O(n1n2).Можно сделать вывод, что, хотя Шутте модифи-цировал алгоритм Вейлера - Азертона более четкимразделением этапов и новым алгоритмом маркировкиребер (edge labeling), его алгоритм обладает более су-щественными ограничениями на входные данные и неизбавился от врожденных недостатков.АЛГОРИТМ ХОЛВЕРДАВходными данными скан-линейного алгоритмаХолверда [12] являются два набора многоугольников.Один из наборов является первым операндом булевойоперации, другой - вторым операндом. Основная идеясостоит в том, чтобы разбить плоскость на секции, на-зываемые закрытыми областями. Закрытые области- это области, которые могут быть описаны простымимногоугольниками (без самопересечений и самопере-крытий).Результат булевой операции может быть получен,если мы сможем выяснить принадлежность каждой иззакрытых областей одному или обоим наборам мно-гоугольников, для этого необходимо вычислить пере-сечения всех сегментов многоугольников.Можно выделить следующие основные этапы ал-горитма:Шаг 1. Конвертация всех многоугольников в гра-фы. Один многоугольник становится одним графом.Шаг 2. Объединение всех графов в один большойграф. Такой граф идеален для скан-линейного алго-ритма, так как ссылки графа могут быть отсортирова-ны без потери структуры отображения. Только ссыл-ки получат другой порядок в списке, позиция же уз-лов не изменится. Следует заметить, что каждаяссылка в графе получает уникальный номер, содер-жащий информацию принадлежности тому или иномумногоугольнику.Шаг 3. Вычисление точек пересечения между гра-фами, используя скан-луч, и вставка их как дополни-тельных вершин или сегментов. Метод скан-луча ис-пользуется несколько раз в этом алгоритме. Идея со-стоит в сканировании изображения вертикальнымскан-лучом. Скан-луч - это пространство между двумяпоследовательными вертикальными скан-линиями.Скан-линия генерируется каждым узлом в графе. Впервую очередь, все начальные узлы ссылок графа сор-тируются по минимальной X координате (если X оди-наково, то по Y). Начальный узел одной ссылки являет-ся всегда конечным узлом другой ссылки просто пото-му, что все многоугольники являются замкнутыми пет-лями. То есть, когда мы генерируем скан-линию длякаждого начального узла всех ссылок, можно бытьуверенным, что все узлы графа будут пройдены.Шаг 4. Установка соответствующих флагов сег-ментов одновременно для всех булевых операций, ис-пользуя скан-луч.Шаг 5. Получение для данной булевой операциирезультирующих многоугольников. В принципе, наданном этапе необходимо найти подходящую ссылку,помеченную для данной операции, и двигаться посвязанным с первой ссылкам, которые также помече-ны для этой операции. Когда мы снова доходим достартовой ссылки, можно извлекать один много-угольник, и так далее, пока не будут получены всемногоугольники.Данный этап выполняется за пять шагов:Шаг 5.1. Уничтожение ненужных ссылок - удале-ние ссылок, для которых не установлен флаг участияв данной булевой операции.Шаг 5.2. Выделение внутренних и внешних конту-ров (рис. 7) из общего графа и помещение их в списокграфов. На внутренние контуры ставится отметка«дыра».Шаг 5.3. Создание одного графа - слияние всехконтурных графов обратно в один граф (необходимодля связывания «дыр» с помощью скан-луча).Шаг 5.4. Связывание «дыр» - использование скан-луча для связывания внутриконтурных графов свнешнеконтурными.Шаг 5.5. Выделение всех связанных графов(внешний и внутренний контур как один граф) из об-щего графа.Шаг 5.6. Конвертация графов обратно в много-угольники.внешний контурвнутр. контурвнутренний контурсвязанный полигонРис. 7. Внутренние и внешние контуры многоугольникав алгоритме ХолвердаИз недостатков алгоритма следует отметить то, чтона входе нельзя использовать самопересекающиесямногоугольники. Однако оригинальность, высокаяскорость работы, корректное округление координат то-чек пересечения и довольно высокая вычислительнаяустойчивость позволяют выделить его из общего ряда.АЛГОРИТМ МАРГАЛИТА - КНОТТАА. Маргалит и Г. Кнотт, авторы одноименного ал-горитма, обратили внимание на то, что многие алго-ритмы пересечения, объединения и разности много-угольников не очень практичны, не способны обраба-тывать сложные случаи, сложны в реализации, ипредложили свой алгоритм, ориентируясь, в первуюочередь, на эффективность и простоту реализации[10]. Алгоритм делится на две основные стадии. Пер-вая стадия - это классификация линейных сегментоввходных многоугольников, а вторая - конструирова-ние результирующих многоугольников.В первую очередь, алгоритм классифицирует ори-гинальные вершины каждого многоугольника на нахо-ждение внутри, снаружи или на границе другого мно-гоугольника. Затем ищутся все точки пересечения ме-жду многоугольниками. Для каждого многоугольникаоригинальные вершины вместе с точками пересеченияпомещаются в такую структуру данных, что две сосед-ние точки определяют оригинальное ребро или частьоригинального ребра результирующего многоугольни-ка (или, иначе говоря, реберный фрагмент).Далее алгоритм классифицирует реберные фраг-менты одного многоугольника на нахождение внутри,снаружи или на границе другого многоугольника.Множество реберных фрагментов многоугольника Qделится на три подмножества, в зависимости от по-ложения относительно многоугольника P. Эти тримножества реберных фрагментов обозначаются какFpin(Q), Fpon(Q) и Fpout(Q). Множество граничныхреберных фрагментов Fpon(Q) в дальнейшем можетбыть разбито на две части, в зависимости от того, в туже или противоположную сторону фрагментам P на-правлены фрагменты Q. Эти множества обозначаютсякак Fpon(Q) и Fpon(Q). Это тонкое деление по-зволяет нам создавать только регулярные результи-рующие многоугольники, для которых необходимо неиспользовать реберные фрагменты из множестваFpon(Q).Классифицированные реберные фрагменты сохра-няются в структуре данных, позволяющей быстро вы-полнять операции поиска и удаления. После созданиякаждого результирующего многоугольника его вер-шины помещаются в выходной массив, а его ребер-ные фрагменты удаляются из структуры данных длятого, чтобы приготовиться для конструирования сле-дующего результирующего многоугольника.Каждый результирующий многоугольник создает-ся при помощи последовательного поиска следующе-го реберного фрагмента, пока не будет найден фраг-мент, вторая конечная точка которого посещается вовторой раз. На этой точке результирующий много-угольник найден.Этот алгоритм относительно прост и практичен.При реализации можно использовать хэш-таблицы идругие простые структуры данных. Элементарныеманипуляции с этими структурами данных произво-дительны, следовательно, минимизируется время итребуемый объем памяти. В алгоритме не нужно об-рабатывать большое число специальных случаев, ипоэтому он может легко работать с любой парой вер-шинно-полных многоугольников. Трудоемкость алго-ритма составляет в худшем случае O(n2), однако напрактике она может быть значительно улучшена всреднем до O(nlogn).ТРИАНГУЛЯЦИОННЫЙ АЛГОРИТМОсновная идея алгоритма построения оверлеевмногоугольников с помощью триангуляции [13] за-ключается в построении триангуляции с ограниче-ниями, где в качестве структурных линий выступаютстороны исходных многоугольников, а затем объеди-нения некоторых треугольников в искомый много-угольник.Отметим, что при построении триангуляции авто-матически решается задача поиска точек пересеченияи разбиения сторон многоугольников, возникающаяво всех других алгоритмах построения оверлеев.В общем виде алгоритм можно записать следую-щим образом (рис. 8):а дAB A ∪ B A ∩ B B \ AA \ Bб вг еРис. 8. Построение оверлеев: а - исходные многоугольники;б - триангуляция с ограничениями; в - объединение; г - пе-ресечение; д и е - разности многоугольниковШаг 1. Стороны исходных многоугольников А и В(рис. 8,а) передаются в качестве структурных линий валгоритм построения триангуляции с ограничениями(рис. 8,б).Шаг 2. Каждый треугольник триангуляции клас-сифицируется по признаку попадания внутрь А и В.Шаг 3. Каждый треугольник Ti полученной триан-гуляции классифицируется в зависимости от вы-полняемой операции.Вариант 1 (объединение):если Ti A или Ti B, то ci:=1, иначе ci:=0.Вариант 2 (пересечение):если Ti A и Ti B, то ci:=1, иначе ci:=0.Вариант 3 (разность):если Ti A и Ti B, то ci:=1, иначе ci:=0.Шаг 4. Все треугольники, имеющие ci:=1, объе-диняются в один многоугольник, который выбираетсяв качестве результата (рис. 8,в-е). Конец алгоритма.Для выполнения первого шага алгоритма можновоспользоваться любым алгоритмом построения три-ангуляции с ограничениями. Обзор таких алгоритмовприведен, например, в [14].В целом трудоемкость первого шага составляет вхудшем случае O(nlog(n1+n2)), а в среднем - O(n).Трудоемкость третьего шага, очевидно, является ли-нейной - O(n). Трудоемкость второго и четвертогошагов составляет также O(n).Таким образом, в целом алгоритм построения овер-леев на основе триангуляции имеет в худшем случаетрудоемкость O(nlog(n1+n2)), а в среднем - O(n).В целом можно сказать, что в связи с достаточновысокой алгоритмической сложностью триангуляци-онного алгоритма на простых видах исходных данныхс небольшим количеством вершин он зачастую усту-пает по скорости другим алгоритмам. Однако насложных многоугольниках с большим количествомвершин в исходных многоугольниках он существеннопревосходит все остальные алгоритмы.ЛИНЕЙНО-УЗЛОВОЙ АЛГОРИТМОсновная идея рассматриваемого алгоритма [15]заключается в предварительном построении линейно-узловой модели - геометрического планарного графаспециального вида, ребра которого должны соответ-ствовать отрезкам исходных границ полигонов (про-исхождение вводимого автором термина «линейно-узловой» связано с используемыми в геоинформатикепохожими топологическими моделями данных - по-крытиями, называемыми также линейно-узловымимоделями).Затем после построения графа производится клас-сификация ребер графа по признаку вхождения в ре-зультирующий полигон. Для классификации всех ре-бер требуется умение выполнять две операции: 1) оп-ределять расположение полигона относительно ребралинейно-узловой модели и 2) определять, попадает линекоторое ребро на границу, внутрь или вне полигона.На последнем этапе алгоритма выполняется сбор-ка отрезков графа в последовательность отрезков гра-ницы требуемого полигона. Для этого достаточно по-сле классификации пометить входящие в результатребра как непройденные, а остальные - как пройден-ные и запустить алгоритм выделения контуров.Обратим внимание, что в результате работы пред-ложенного алгоритма будет построен полигон, в ко-тором контуры не будут взаимно- и самопересекаться,и каждый контур будет задан в таком порядке обходаточек, что полигон всегда находится справа по ходуобхода.Линейно-узловой алгоритм построения оверлеевпозволяет явно учесть многочисленные тонкие эф-фекты, возникающие на пороге точности вычислений.Данный алгоритм имеет такой же порядок трудоемко-сти, что и алгоритм Маргалита - Кнотта [10], но всреднем в 1.5 раза медленнее последнего. Тем не ме-нее предлагаемый алгоритм имеет несколько боль-шую область определения и достаточно простуюструктуру для программной реализации.ЗАКЛЮЧЕНИЕВ таблице приведены сравнительные характери-стики всех вышеописанных алгоритмов.К недостаткам большинства из них стоит отнестинедостаточно высокую вычислительную устойчи-вость, нерешенные численные проблемы, связанные сокруглением. Многие алгоритмы реализуют наборопераций, не являющийся замкнутым, так как в ре-зультате их выполнения могут получаться контуры ссамокасаниями, что неприемлемо в качестве исход-ных данных.Одним из наиболее простых алгоритмов можнопризнать алгоритм О'Рурка, однако он обрабатываеттолько выпуклые многоугольники. Можно выделитьтакже алгоритмы Леонова и Холверда - наряду с ус-тойчивой и быстрой работой, способностью обраба-тывать общие многоугольники, в них решены про-блемы появления «посторонних пересечений», возни-кающих при округлении точек пересечения.Однако из-за высокой скорости работы и лучшейвычислительной устойчивости для практическогоприменения стоит рекомендовать триангуляционныйалгоритм в случае относительно большого числа уз-лов исходных многоугольников и линейно-узловойалгоритм для меньшего числа.Сравнительные характеристики различных алгоритмов построения оверлеев: n1 - количество вершинпервого многоугольника A; n2 - второго (B); n0 - количество новых точек пересечения сторон двухмногоугольников; z - общее число контуров многоугольников A и В n = n1+ n2+ n0Поддерживае-мые Алгоритм операции  /Тип исходныхмногоугольниковПростотапрограмм-ной реали-зацииУстой-чи-востьСко-рость Трудоемкость ОбщаяоценкаСазерленда - Ходжмана + - - Один выпуклый,другой общий 5 3 4 O(n1n2logn2) 3О'Рурка + + + Выпуклые 5 4 5 O(n) 5Вейлера - Азертона + + +Простые с ориен-тированными кон-турами3 3 4 O(nlog(n1+n2)) 3Леонова + + + Общие 4 5 4 O((n1+n2)log(n1+n2) ++n0+zlog(n1+n2 )) 5Шутте + - + Простые 4 3 4 O(n1n2) 3Холверда + + + Общие 3 5 4 O(nlogn) 4Маргалита

Скачать электронную версию публикации