Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Поэтому оценка корректировки в случае (1.1), так же как и в случаях (1.2), (2.3) и (2.4), равна O(N). Наконец, все корректировки F и L заканчиваются нахождением точек а/ и w". Следовательно, время работы всего алгоритма пропорционально числу вершин Р и доказана
Теорема 7.13. Ядро N-вершинного многоугольника можно вычислить за оптимальное время Q(N).
7.3. Трехмерные приложения
373
7.3. Трехмерные приложения 7.3.1. Пересечение выпуклых полиэдров
Задача ставится следующим образом:
Задача С.1.6 (ПЕРЕСЕЧЕНИЕ ВЫПУКЛЫХ ПОЛИЭДРОВ). Даны два выпуклых полиэдра — /5 с L вершинами и Q с М вершинами. Требуется построить их пересечение.
Для доказательства выпуклости полиэдра, образованного пересечением Р П Q, используются те же аргументы, что и в теореме 7.2. Самый грубый подход к вычислению Р П Q состоит в проверке пересечения каждой грани Р с каждой гранью Q. Если такие пересечения существуют, то результат можно просто построить; если же попарных пересечений нет, то P(]Q пусто или один из полиэдров расположен внутри другого. Поскольку поверхность каждого полиэдра топологически является планарным графом, то из теоремы Эйлера о планарных графах следует, что изложенный подход может потребовать 0((L + -f- М)2) времени').
Коль скоро этот подход отвергается как негодный, другой попыткой может стать адаптация к случаю трех измерений тех двух методов построения пересечения пары выпуклых многоугольников, которые были приведены в разд. 7.2.1. Метод Шей-моса — Хоуи [Shamos, Ноеу (1976)] (разбиение плоскости и вычисление пересечения Р и Q в каждой области этого разбиения) можно было бы обобщить, разрезая пространство семейством параллельных плоскостей, каждая из которых проходит через вершины Р U Q. Однако в каждом из получающихся при этом слоев пространства (или «полосах», как их часто называют) соответствующая порция каждого полиэдра не является простым геометрическим объектом, как было в плоском случае. В действительности получается некий «блин», ограниченный с двух сторон плоскими многоугольниками, в каждом из которых может быть 0(|число граней|) ребер. Поэтому этот подход привел бы также к О((L 4- М)2)-алгоритму. Что же касается метода [O'Rourke, Chien, Olson, Naddor (1982)], то обобщить его кажется невозможно.
Абсолютно иной подход, который, конечно, можно успешно приспособить и к случаю двух измерений, был предложен Мал-лером и Препаратой [Muller, Preparata (1978)] и обсуждается ниже. Альтернативный и очень привлекательный подход [Hertel, Melhorn, Mantyla, Nievergelt (1985)], основанный на простран-
') Из теоремы Эйлера следует лишь, что число граней F не превосходит 0(N), где N — число вершин графа. В самом деле, по формуле (1.2) F < ^ 2N — 4. Отсюда следует, что более точная оценка времени грубого алгоритма равна O(LM). — Прим. перев.
374
Гл. 7. Пересечения
ственном заметании, был предложен совсем недавно, и он будет кратко рассмотрен в разд. 7.4.
Центральная идея метода Маллера — Препараты состоит в том, что если одна из точек пересечения — р известна, то пересечение можно построить с использованием известной техники двойственности. Действительно, если точка р из Р П Q существует, то простым переносом можно совместить с ней начало координат. Поэтому можно предположить, что начало пространственной системы координат лежит внутри как Р, так и Q. Обозначая через х\, х2 и хъ координаты в этом пространстве, свяжем с каждой гранью / из Р или Q некое полупространство:
Щ (!) х, + п2 (!) х2 + п3 (f) x3^d (f). (7.12)
Поскольку любая точка из Pf\Q удовлетворяет всем неравенствам (7.12) для каждой грани каждого полиэдра, а начало координат (0, 0, 0) является точкой из Р |~| Q, то все неравенства можно нормировать так, что d(f) = 1. (Напомним, что по предположению начало координат лежит внутри как Р, так и Q.)
Если теперь интерпретировать тройку (m(/), n2(f), n3(f)) как точку, то получится эффективно определенное инволютив-ное преобразование между плоскостями граней (т. е. плоскостями, которые несут грани) и точками. Это преобразование является обычным преобразованием двойственности (поляритетом) относительно единичной сферы с центром в начале координат, которое обсуждалось в разд. 1.3.3. При таком преобразовании точки на расстоянии / от начала координат отображаются на плоскости на расстоянии 1/7 от этого начала и наоборот.
Введем обозначение б( ) для этого преобразования, т. е. 8(р) обозначает плоскость, двойственную к точке р, а б(я)— точку, двойственную к плоскости я.
Двойственное преобразование выпуклого многоугольника имеет смысл только тогда, когда он содержит внутри себя начало координат. Действительно, в этом случае имеется следующее важное свойство:
Лемма 7.2. Пусть Р — выпуклый многоугольник, содержащий начало координат, a S —множество точек, двойственных к плоскостям, несущим грани Р. Тогда любая точка р, лежащая внутри Р, отображается в такую плоскость 8(р), которая не пересекается с полиэдром conv(S).
Доказательство. Пусть неравенство ai*i + ft,-*2 + Ci*3<l определяет полупространство, ограниченное гранью /, из Р, при /= 1, .., |5|. (Напомним, что это полупространство содержит
