Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
ресекающихся циклов. ~ ~, ¦6)0 ' " Ys
на втором этапе ЭТИ вер- рИС. 8.12. Иллюстрация к задаче построе-ТИКальНые ребра соеди- ния контура объединения прямоугольников.
няются горизонтальными
ребрами для формирования ориентированных циклов контура [Lipski, Preparata (1980)].
Обозначим через (х; Ь, г) вертикальное ребро с абсциссой х, для которого b и t (b <С г) являются соответственно нижней и верхней ординатами; аналогично (у; I, г) обозначает горизонтальное ребро с ординатой у, для которого / и г (/ < г) являются соответственно левой и правой абсциссами.
Для получения множества V просканируем слева направо абсциссы, соответствующие вертикальным сторонам прямо-
Алгоритм лучше всего описать неформально, на примере. Он состоит из двух главных этапов. На первом этапе определяется множество V, состоящее из вертикальных ребер контура (ребра от е\ до ею на рис. 8.12);
Н х7 х9
х6
416
/л. 8. Геометрия прямоугольников
угольников. Для произвольной абсциссы с сечение 3(c) объединения F вертикальной прямой х = с является набором непересекающихся интервалов. Такое сечение не изменяется между двумя последовательными вертикальными сторонами прямоугольников, но корректируется при сканировании всякий раз, когда встречается такая сторона. Если s является левой вертикальной стороной с абсциссой с для какого-нибудь прямоугольника R, то участок контура F, определяемый s, задается s[\3(c-), где 3(с_) обозначает объединение интервалов, лежащих непосредственно слева от абсциссы с, а 3(с_) обозначает его теоретико-множественное дополнение. Аналогично, если s — правая вертикальная сторона R с абсциссой с, то вклад s в контур равен s{]3 (с+); смысл обозначений очевиден. Запоминание и корректировка сечения 3 и эффективное определение sn^(c-) или s()3(c+) являются наиболее сложной частью алгоритма и будут рассмотрены позднее.
Предположим пока, что множество V уже получено и в согласии с принятым условием об ориентации контура каждое ребро V направлено вверх или вниз в зависимости от того, принадлежат его ординаты соответственно правой или левой стороне прямоугольника.
Заметим теперь, что если множество вертикальных ребер V известно, то горизонтальные ребра можно определить прямым методом. Действительно, если (у;х\,х2)— горизонтальное ребро (рис. 8.13), то существуют два вертикальных ребра с абсциссами х\ и х2 соответственно, причем у каждого из них один из концов имеет ординату у. Предположим далее, что для вертикального ребра е-, = (*/; b,-, tj) из V сформированы две тройки <*/, Ъ,\ t,} и <*/, tj] bj). Каждую из этих троек следует считать точкой (координаты которой совпадают с первым и вторым элементами тройки), в совокупности эти две точки являются концами ребра ер, третий член каждой тройки является просто ссылкой на противоположный конец е,-. Упорядочим множество троек лексикографически по возрастанию (сначала по ординате, затем по абсциссе). Для примера на рис. 8.12 получается следующая последовательность:
(х2, Ъ2; г2><*4, b4; tt)(xit U; b4)(xg, b9; tg)(x9, /„; b9)(xm bl0', tl0) <*5. h; t5)(x7, b7; t7)(xu 6,; t,){x2, t2; b2)(x5, t5; bs)(x7, b7; t7) <*„ bl){x3, b3; t3){x6, b6; /6><*8, b8; t8)(xs, /8; b8)(xl0, f10; bl0) (x3, t3; b3)(x6, t6\ b6).
Причина выбора такого расположения заключается в следующем. Пусть а\, а2, ар (р четно) представляет собой результирующую последовательность. Легко видеть, что гори-
8.5. Контур объединения прямоугольников
зонтальные ребра контура могут быть получены как отрезки, соединяющие вершины a2k~\ и a2k для k = 1, 2, ..., р/2. Более точно, пусть С2Й-1 = (.1, У- У\>, a2k = (г, у: у2). Горизонтальное ребро {у; I, г) ориентируется слева направо, если ребро, соответствующее тройке (1,у;у\У, ориентировано вниз и у < у\ или если </,#;«/]> ориентировано вверх1) и ух <С у; иначе ребро (у; I, г) ориентируется справа налево. Для вышеприведенного примера пара (а{, а2) = ((х2, b2: t2), <л-4, Ь4: /4>) при Ь2 = Ь\ порождает горизонтальное ребро (Ь2;х2,х^), ориентированное слева направо, поскольку ребро е2, соответствующее (х2, Ьг\ t2}, направлено вниз и b2 < t2; напротив, пара (аи, ai8) = (<x8, f8: Ь&У, <хю, tm йю» при t8 = ho порождает ребро (4;*8>*ю), ориен тированное справа налево, поскольку е8 направлено вверх, а ts <? bg. Очевидно, что за один проход по последовательности
а\.....ар можно породить все
горизонтальные ребра и дважды связать каждое из них с двумя смежными вертикальными ребрами. Результирующие списки дают в точности искомые циклы контура. Кроме того, если цикл посредством его ребра
Рис. 8.13. Любое горизонтальное ребро смежно с парой вертикальных ребер.
идентифицировать каждый с минимальной абсциссой, то направление такого ребра определяет, будет ли этот цикл границей дыры (тогда указанное ребро направлено вверх) или участком внешней границы (тогда указанное ребро направлено вниз).
Оценим теперь работу алгоритма. Читателя не должна беспокоить повторная операция сортировки 2р элементов (лексикографическое упорядочение, которое было описано ранее). Действительно, путем предварительной сортировки абсцисс и ординат сторон прямоугольников (за 0(N\ogN) операций) можно нормализовать эти координаты и заменить их на последовательные целые числа. После этого 2р троек, которые нужно упорядочить лексикографически, будут состоять из целых чисел. Используя стандартный метод сортировки вычерпыванием [Knuth (1973)], получаем искомое упорядочивание за время О(р); еще О(р) времени используется для порождения горизонтальных ребер и контурных циклов.
