Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
7.3. Трехмерные приложения
375
начало координат.) Теперь рассмотрим любую точку р = = (х\, х2, хг), лежащую внутри Р. Имеем atxx + btx2 + с(х3 < 1, i = 1, 2, ..., \S\.
Эти неравенства можно интерпретировать следующим образом. Плоскость б(р), двойственная к р, имеет уравнение х\Х\ + + Х2Х2 + Х3Х3— 1; если взять точку б (я,), двойственную к плоскости я;, несущей грань то данные неравенства означают, что все точки б (я,) при /= 1, 2, \S\ лежат по одну сторону от плоскости б(р) и не лежат на ней, т. е. б(р) не имеет пересечений с conv(S). Что и требовалось доказать.
Полученный результат приводит к следующему утверждению:
Теорема 7.14. Если Р — выпуклый полиэдр, содержащий начало координат, то таким же является и двойственный к нему полиэдр Р<в>.
Доказательство. Пусть я, — плоскость, несущая грань f, из Р. Определим точечное множество 5А{5(%): i= 1, \S\} и рассмотрим его выпуклую оболочку CH(S). Докажем, что каждая точка 5 является вершиной СН(5). Действительно, если б (я,) лежит внутри conv(S), то я, не имеет пересечений с Р по лемме 7.2, а это противоречит тому, что щ несет грань fi. Поэтому CH(S) — это двойственный к Р полиэдр Что
и требовалось доказать.
Приведенное доказательство демонстрирует также тот факт, что если Р содержит начало координат, то любая внешняя к Р плоскость отображается в точку внутри Р(6> и наоборот. Хотя эти соображения приложимы ко всем полиэдрам, удовлетворяющим предположениям теоремы 7.14, далее будем считать, что начало координат лежит строго внутри Р (и, следовательно, Р<в>). Читатель может проверить, что отсюда следует ограниченность как Р, так и Р<в).
Пусть и Vty -обозначают множество вершин соответственно Р(6) и Q<6'. Если вспомнить, что каждый элемент V1p U является двойственным к какой-нибудь из плоскостей, несущих грань одного из исходных полиэдров, и заметить, что Pf\Q — это множество таких точек, которые одновременно лежат во всех полупространствах, определенных этими гранями и содержащими начало координат, то можно утверждать, что полиэдр PRQ является двойственным к выпуклой оболочке V'p' U V^K Значит, для вычисления Pf]Q можно использовать алгоритм Препараты —Хонга (см. разд. 3.4.3), который опре-деляет conv(l/<p«>lJ У«>) за время 0(N\ogN) (где NAL + M);
376
Гл. 7. Пересечения
если затем взять фигуру, двойственную к этому результату, то получится искомый полиэдр. Двумерной иллюстрацией этого метода служит рис. 7.33.
Здесь необходимо сделать замечание. Изложенный метод включает обработку множества троек {(т (/), n2(f), п3(/): / — грань Р или Q}. Эти тройки интуитивно интерпретировались как точки, но с тем же успехом их можно было бы считать плоскостями. Единственной причиной предпочтения первой интерпретации является то, что получаемый при этом метод полностью
Рис. 7.33. Иллюстрация метода построения пересечения двух выпуклых многоугольников с использованием двойственного подхода. Два исходных многоугольника изображены тонкими сплошными линиями, а двойственные им фигуры (также выпуклые многоугольники) — штриховыми линиями. Опорные прямые выпуклой оболочки объединения последних фигур показаны жирными линиями, каждая из которых является двойственной к одной из вершин искомого пересечения (двойственные элементы помечены одинаково.
опирается на интуицию, а при второй интерпретации это менее заметно. Следовательно, двойственность поляритета не изменяет природы геометрических объектов (в отличие от преобразования инверсии —см. разд. 6.3.1.1), но существенно помогает нашей интуиции. Итак, если одна точка внутри Pf\Q известна, то пересечение можно построить стандартными алгоритмами. Но как найти такую точку, если P(]Q, вообще говоря, непусто? Поступим следующим образом.
Пусть дан выпуклый полиэдр Р, рассмотрим множество его опорных плоскостей, параллельных оси хз, которые для краткости назовем вертикальными. Пересечением Р с его вертикальными опорными плоскостями будет, вообще говоря, кольцеобразная область R(P) на поверхности Р, которая в невырожденных случаях сводится к кольцу его ребер. Проекцией R(P) на плоскость (л'ь лг2) является выпуклый многоугольник Р* (рис. 7.34), совпадающий с выпуклой оболочкой проекций точек из Р на эту плоскость,
7.3. Трехмерные приложения
377
Область Р(Р) легко вычисляется. Для любой грани ft из Р нормалью к ft является вектор {пи (f,), n2(/i), «з (/*))• Он перпендикулярен fi, и направлен внутрь Р. Пусть fi и f; —грани, смежные ребру е из Р. Тогда ее^(Р) в том и только том случае, когда
лз (fi) «3(f/)<0. (7.13)
Следовательно, начнем с обхода ребер Р до тех пор, пока не обнаружим такое ребро е, которое принадлежит R(P), проверяя условие (7.13). Затем выберем одну из двух вершин е, назвав ее v. Среди ребер, инцидентных v, есть одно или два новых
Рис. 7.34. Выпуклый полиэдр Р, кольцеобразная область R(P) и многоугольная проекция Р*.
ребра, отличных от е, которые принадлежат R(P) и могут быть без труда найдены. (Предполагается, конечно, что поверхность Р — планарный граф — представлена структурой данных типа РСДС, которая была описана в разд. 1.2.3.2.) Поэтому можно продолжить построение R(P), которое будет завершено при повторной встрече исходного ребра е. После вычисления Р(Р) можно тривиально получить Р*. Итак, получены два первых шага алгоритма:
