Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Шаг 1. Построить Р* и Q*. (Это займет O(N) времени.) Шаг 2. Построить пересечение многоугольников Р* и Q* (используя любой из линейных по времени алгоритмов, описанных в разд. 7.1). Если P*f|Q*=0, то останов, ибо PftQ при этом также пуст. (Этот шаг займет O(N) времени.)
Если P*(]Q* Ф 0, то обозначим через 2) замкнутую (выпуклую) область, ограниченную Р* fl О*- Через каждую точку р = \х\, х2) из 2> проведем вертикаль. Ее пересечением с Р является отрезок еР(р); аналогично определяется и eQ{p) (как
378
Гл. 7. Пересечения
вр{р), так и eQ(p) могут выродиться каждый в единственную точку). Наша цель состоит в том, чтобы решить вопрос о существовании некой точки р из 2), для которой вр(р) и е<э(р) перекрываются (рис. 7.35). Полагая без потери общности, что существует такая точка ие2), для которой низ отрезка еР(и) лежит выше верха отрезка е<з(м), определим ближние стороны Р и Q как множества точек соответственно низ[ер(«)] и
V и ccz
Рис. 7.35. Поперечное сечение Р и Q плоскостью Х\ =х\. Иллюстрация к определению еР( ), eQ( ) и а( ).
верх[е<з(ц)] и функцию d(u), именуемую вертикальным расстоянием, следующим образом:
й(ы):=низ [eP(u)] — Btpx[eQ(u)]. (7.14)
Итак, следует решить вопрос о существовании такой точки ие25, чтобы d(u)^ 0. Ответ на этот вопрос будет, разумеется, получен, если определить такую точку й, в которой достигает минимума функция d: d (й) = min d (и).
и<=?>
Очевидно, на практике поиск точки и будет фактически прекращен только при условии, что d(u)>0, причем в этом случае два наших полиэдра не пересекаются. В противном случае этот поиск можно прекратить, как только будет обнаружена некая точка v ?= 2), для которой d(v) ^ 0.
Метод решения данной задачи, который сейчас будет описан, принадлежит Дайеру [Dyer (1980)], а технически он значительно проще первоначального метода [Muller, Preparata
7.3. Трехмерные приложения
379
(1978)] (хотя он и не демонстрирует сколько-нибудь значительного улучшения эффективности).
Прежде всего заметим, что функция d(u) выпукла на Ж). Действительно, пусть Sp —такой участок поверхности Р, на котором Хъ = низ [ер (и)] для ие2); аналогично определяется SQ, где х3 — верх [ее (а)]. Другими словами, SP и SQ — противолежащие стороны двух полиэдров. Если теперь спроецировать Sp на плоскость х3 — 0, то получится планарный граф Gp, состоящий из выпуклых ячеек; аналогично определяется Gg.
Рис. 7.36. Иллюстрация к определениям величин Хи X2{xi) и y(*0-
Представим себе наложение GP и GQ. Результирующий граф G* является пересечением двух плоских карт, а его вершинами являются исходные вершины Gp и Gq (условно именуемые настоящими вершинами) и точки пересечения ребер Gp с ребрами GQ (условно именуемые псевдовершинами). Поэтому область ЯЬ разбивается графом G* на множество выпуклых подобластей. Заметим, что внутри любой подобласти из Gp функция низ[еР(и)] линейна по координатам (хих2) точки и; точно так же, как и функция верх[ед(ы)] внутри любого региона Gq. Поэтому внутри любого региона, образованного графом G* в 2), функция d(u) линейна по хх(и) и х2(и). Более того, функция низ [ер (и)] выпукла вниз, а верх [е^ (и)] выпукла вверх; отсюда следует, что d(u) является функцией выпуклой вниз. Значит, минимум d(u) находится в одной из вершин G*. Заметим, что число вершин графа G* может достигать 0(/V2):
Гл. 7. Пересечения
фактически можно без труда построить два таких планарных графа, каждый из которых имеет по v вершин, чтобы при их наложении получалось (v—I)2 точек пересечения их ребер. Обратимся к рис. 7.36; пусть Х\ будет интервалом \minx\(u), max*! (и)].
Пусть Х2{х\) обозначает интервал
[min х2(и), max х2(и)] для Jc,eX|
ж, («)-*, *, (и)-*,
(т. е. отрезок, получающийся в сечении 2) прямой х\ = Х\). Поскольку d(xux2)= d(u) выпукла в 2>, то по хорошо известному результату из выпуклого анализа [Rockafellar (1970)] функция
Y(*i)A min d(xu х2) при хх<=Х{
будет выпуклой в Х\. Поскольку min y(xl) = min d(u),
то задача свелась к оценке минимума y(xi) на интервале Х\.
Прежде всего отметим, что вычисление y(*i) пРи заданном Х\ выполнимо за время O(N). Рассматривая только один из полиэдров, скажем Р, определим прямым методом за время
Лроходгго поверхности Р
Рис. 7.37. Вычисление функции низ[еР( )] на многоугольнике, образованном в сечении Р плоскостью Х\ = хи производится простым проходом по РСДС.
0{L) значение функции низ[е?(ы)] для точки й в плоскости х3 = 0 на пересечении прямой х\ = х\ с границей Р*. Затем простым проходом по поверхности Р с помощью РСДС можно определить также за время O(L) значения функции низ[е,<()], соответствующие пересечениям каждого ребра из Р с плоскостью xi = xi (рис. 7.37). Таким же способом можно обработать Q за время О(М). Функции низ[сР(и)] и верх[е0(у)] для x\{v) = x\ показаны на рис. 7.38. Значит, функция d{v)
7.3. Трехмерные приложения
381
при se2) и xi(v) = xi вычисляется за время 0(L-\-M) = — 0(N), при этом также вычисляется ее минимум у{х\).
