Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
И действительно, сейчас мы покажем, что существует оптимальный метод [Preparata, Muller (1979); Brown (1978)], который, не относясь к типу «разделяй и властвуй», использует алгоритмы как пересечения полиэдров, так и разделяющей плоскости (см. разд. 7.2.5). Как и описанный метод построения пересечения полиэдров, этот метод основан на активном использовании двойственного подхода по отношению к единичной
384
Гл. 7. Пересе ч
сфере. Необходимо указать, что для упрощения иллюстраций, а в некоторых случаях и просто для опоры на интуицию (иначе нам пришлось бы представлять себе четырехмерные объекты!) все наши примеры будут относиться к двумерным ситуациям. Однако важно подчеркнуть, что это не повлияет на справедливость доказательств.
Общая задача ставится следующим образом:
Задача С.1.7 (ПЕРЕСЕЧЕНИЕ ПОЛУПРОСТРАНСТВ). Найти множество решений (х, у, z) {допустимых точек) для множества из N линейных неравенств:
где a,, bi, Ci и di — действительные числа, не равные одновременно нулю.
Решение ищется в форме описания выпуклой полиэдральной поверхности, ограничивающей область допустимых точек. Качественно это решение может принимать одну из следующих форм (с увеличением размерности):
1. Пустое множество (уравнения (7.15) несовместны).
2. Точка.
3. Отрезок.
4. Выпуклый плоский многоугольник.
5. Выпуклый полиэдр.
Случаи 2, 3 и 4 вырождены; интересны лишь случаи 1 и 5.
Один простой случай получается, когда для всех i=\, ... ..., N выполняется di ^ 0. Действительно, при этом начало координат (0,0, 0) удовлетворяет всем ограничениям, т. е. оно содержится внутри общей области этих полупространств. Тогда, произведя двойственное преобразование плоскости л,, заданной уравнением atx + biy + c,-z + di = 0, в точку (ai/di, bi/diy ct/di) и вычислив за время О (N log N) выпуклую оболочку полученного множества точек, мы построим выпуклый полиэдр, двойственным к которому будет искомое пересечение.
Ситуация становится значительно более сложной, когда di произвольны. Для простоты предположим здесь, что никакие из di не равны нулю, так что множество индексов {1, N) можно разбить на такие два подмножества /+ и /_, что i <= /+, если di > 0, и i'eL если di < 0. Предположим также без потери общности, что di = ±1 ')•
Чтобы понять этот механизм, удобно рассмотреть нашу задачу в однородных координатах, осуществив преобразование
atx + bty + ctz + < 0 при /=1,2,..., N,
(7.15)
(7.16)
') Задача в общей постановке, допускающей di = 0, изложена в работе [Preparata, Muller (1979)].
7.3. Трехмерные приложения
Как было показано в разд. 1.3.2, в котором были введены однородные координаты, любую точку (х, у, z) из Е3 можно интерпретировать как прямую (сх, су, cz, с) из Е4, где ceR. Если обозначить координаты в Е4 через Х\, х%, х3 и х\, то в такой интерпретации обычное пространство Е3 становится гиперплоскостью jc4 = 1 в Е4 (см. рис. 7.40, показывающий аналогию с размерностью, на единицу меньшей). Точно так же если спроецировать гиперплоскость х4 = 1 на единичную гиперсферу
Рис. 7.40. Иллюстрация соответствия между обычными координатами в Е1 (на плоскости хъ = 1) и однородными координатами в Е?. Каждая точка на Е? соответствует прямой, проходящей через начало координат в Е3.
S4, центр которой помещен в начало координат, то каждой точке р из Е3 будет соответствовать единственная точка р* на S4 (при х4>0), получающаяся при пересечении S4 с отрезком, соединяющим р с началом координат О. Точки на S4 с х4 > 0 и х4 < 0 образуют соответственно положительную и отрицательную открытые полусферы; те точки, для которых х4 = 0, экватор, соответствуют бесконечно удаленной плоскости в Е3.
Преобразование координат (7.16) переводит каждое полупространство aix + biy + CiZ + di 0 из Е3 в полупространство
atXi + btx2 + ctxz + d,x4 ^ 0
в ?4, для которого ограничивающая его гиперплоскость проходит через начало координат, а вектор v; = (а,-, с,-, di) нормален к этой гиперплоскости и направлен вне этого полупространства. Указанная гиперплоскость пересекает S4 по «большой окружности» d. Кроме того, ограничение а,х + biy +
Гл. 7. Пересечения
-f- CiZ + di ^ 0 определяет единственную полусферу, ограниченную этой большой окружностью Си Эта полусфера содержит начало координат Е3 тогда и только тогда, когда d, = — 1.
А*»
Рис. 7.41. Пересечением полусфер на S3, которые соответствуют ограничениям (полуплоскостям на Е2), является связная область D на поверхности S3.
Поэтому для заданного множества из N линейных ограничений в Е3 их общая область соответствует связной области 2) (возможно, пустой), лежащей на поверхности 54 (рис. 7.41). Область 2) разбивается на две (возможно, пустые) связные области 2)+ и 2)-, лежащие на соответственно положительной
{Общая наружность)
J6+ (общая внутренность)
Рис. 7.42. Соотношения между областями D+, ?>_, а также общими внутренностью и внешностью (наружностью) для заданных ограничений.
и отрицательной полусферах (рис. 7.42). Теперь предположим, что реализуется проецирование 2) с центром в начале координат, причем 2)+ проецируется на выпуклую область 2)\, лежащую на гиперплоскости х^=\ (т. е. в обычное пространство
