Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Предположим теперь, что рекурсивным образом получены политопы Pi = CH(Si) и P2 = CH(S2). Важно подчеркнуть, что вследствие предварительной сортировки и выбранного способа разбиения результирующего множества (строка 2 в алгоритме СН(5)) политопы Р[ и Р2 не пересекаются. Слияние Pi и Р2 можно выполнить с помощью следующих операций (рис. 3.29 иллюстрирует идею этих операций):
1. Построить «цилиндрическую» триангуляцию 3~, опирающуюся на Р\ и Р2 по некоторым контурам Ех и Е2 соответственно2).
2. Удалить из Pi и Р2 части, оказавшиеся «скрытыми» в результате построения триангуляции Ф.
Здесь использованы не определенные формально термины «цилиндрическая» и «скрытые» в расчете на их интуитивное понимание в соответствии с рис. 3.29. Оставаясь на интуитивном уровне, построение триангуляции можно рассматривать как операцию «заворачивания подарка»: с помощью 3~ мы как бы заворачиваем в один «сверток» одновременно и Рь и Р2. Хотя ?Г может иметь O(N) гиперграней, а каждый шаг заворачивания в общем случае требует O(N) операций, использование особенностей трехмерных политопов позволяет, как будет показано далее, сделать существенное упрощение.
Рис. 3.29. Иллюстрация основной идеи метода. Триангуляция 9~ образуется в результате «заворачивания» выпуклых оболочек Р, и Р2-
') Здесь термин «грань» используется в общепринятом для плоских графов смысле. Однако в оставшейся части этого раздела будет использоваться термин «гипергрань», чтобы подчеркнуть, что они являются (d—1)-мерными множествами.
2) Мы неявно предполагаем, что на каждом этапе обработки мы имеем симплициальные (триангулированные) политопы. Как будет видно из дальнейшего, это несущественно влияет на общность результата.
3.4. Выпуклые оболочки размерности большей двух
175
Построение триангуляции 3~ начинается с определения некоторой ее гиперграни или ее ребра. Хотя имеются несколько способов решения этой задачи, довольно удобный способ основывается на построении проекций (например, на плоскость (*i> х2)), являющихся многоугольниками, каждого из политопов (рис. 3.30). Обозначим через Р'1 проекцию Pi на плоскость (хи х2) (i = 1, 2). Теперь можно воспользоваться нашим люби-
Рис. 3.30. Начальный и последующие шаги процедуры построения Т.
мым алгоритмом (см. разд. 3.3.5), чтобы построить общую опорную прямую к Р[ и Р'2 и получить тем самым на плоскости (хи х2) ребро е', являющееся проекцией ребра е триангуляции ST. Имея ребро е, можно начать построение 3", выбрав в качестве опорной плоскость, проходящую через ребро е параллельно оси Хг.
На очередном шаге построения ST в качестве базы используется последняя построенная гипергрань триангуляции 0". Будем использовать при обозначении вершин политопа Р\ букву а, а для Р2 — букву Ъ. Пусть гипергрань (а2, Ь2, а.\) является базовой на текущем шаге (на рис. 3.30 она заштрихована). Теперь среди вершин, смежных с а2, необходимо выбрать вершину а, так чтобы гипергрань (а2, Ь2, а) образовала наибольший выпуклый угол с (а2, Ь2, ах) среди всех гиперграней (а2, b2, v), где v — вершина, смежная с а2, и v ф а\. Аналогичным образом среди вершин, смежных с Ь2, выберем вершину б. По причинам,
176
Гл. 3. Выпуклые оболочки: основные алгоритмы
которые станут понятными в дальнейшем, эти сравнения называются сравнениями типа 1.
Теперь, когда выявлены два «претендента» — (а2, Ь2, а) и (а2, Ь2, 6), делается заключительное сравнение, называемое сравнением типа 2. Если (а2, Ь2, а) образует с (а2, Ь2, больший выпуклый угол, чем (а2, fo2, 6), то а добавляется к ?Г (в противном случае добавляется 6), и на этом очередной шаг заканчивается. Описанный порядок выполнения сравнений является, как будет видно далее, эффективным способом реали-т,_ зации шага «заворачивания по-
дарка» вокруг ребра (а2,Ь2).
Эффективная реализация описанного только что механизма последовательного построения граней триангуляции основывается на следующих соображениях. В РСДС можно эффективно проходить ребра, инцидентные некоторой вершине, в порядке обхода по часовой стрелке или против нее. Для большей конкретности обратимся к рис. 3.31. Предположим, что вершина b и ребро (Ь, а) триангуляции ?Г были добавлены последними. Пусть (b\,b)—ребро контура Е2, входящее в вершину Ь. Не теряя общности, можно предположить, что нумерация ребер, инцидентных вершине Ь, и их конечных вершин b], Ь2, . . . , bk аналогична показанной на рис. 3.31 (где k = 7). Подобное же предположение имеет место и относительно вершины а. Пусть (bs, b, а)—гипергрань, образующая наибольший выпуклый угол с (b\x Ь, а) из всех (&,, Ь, а) с i = 2, ..., k (в нашем примере s = 4). Первое важное соображение состоит в том, что любое ребро (b, bi) при 1 < i < s оказывается внутри выпуклой оболочки CH(Pi []Р2), и поэтому его можно исключить из дальнейшего рассмотрения. Что касается вершины а, то заметим, что множество инцидентных ей ребер было частично просмотрено на более раннем этапе работы алгоритма, так как вершина а была получена прежде, чем вершина Ь. И как следствие сказанного выше просмотр ребер, инцидентных вершине а, следует начинать с последнего из просмотренных ребер, так как все другие были удалены (на рис. 3.31 это ребро (а, а4)).
