Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Свойство (8.1) позволяет предложить два эквивалентных алгоритма для вычисления замыкания заданной фигуры F. Например, равенство СВЮЗ (F) = ЮЗ (СВ (F)) позволяет вычислить сначала СВ-замыкание F, а затем завершить решение этой задачи путем вычисления ЮЗ-замыкания для CB(F). Эти две задачи сильно упрощаются, когда F является объединением изотетичных прямоугольников, поскольку верхний и нижний контуры любой компоненты СВЮЗ (F) являются при этом х-мо-нотонными ступенчатыми кривыми. Данный алгоритм будет работать следующим образом. Он состоит из двух плоских заметаний в противоположных направлениях. Первое из них, проводимое слева направо, строит СВ-замыкание для фигуры F (объединения изотетичных прямоугольников), т.е. оно определяет СВ-замкнутые компоненты связности. Второе плоское заметание (справа налево) строит ЮЗ-замыкание для СВ(/7), т. е., начиная со связных компонент СВ(/?), оно определяет в результате компоненты K03(CB(F)) (и тем самым CBK>3(F)).
Компонента CB(F) называется активной (при плоском заметании), если ее пересекает заметающая прямая; очевидно, что компонента СВ (F) активна тогда и только тогда, когда она содержит по крайней мере один прямоугольник из F, пересекаемый заметающей прямой (он называется активным прямоугольником).
Во-первых, исследуем те две основные ситуации, которые встречаются при плоских заметаниях (для конкретности: речь будет идти о заметании слева направо, которое строит CB(F)). Очевидно, что точками событий являются абсциссы вертикальных сторон прямоугольников. Если текущим событием является встреча с левой стороной, то производятся следующие действия: (1) инициализируется активная компонента, или (2) расширяется активная компонента, или (3) объединяются две или более активные компоненты; с другой стороны, завершение работы с активной компонентой (и ее деактивация) может произойти только при встрече с правой стороной какого-нибудь прямоугольника. Активная компонента характеризуется актив-
8.6. Замыкание объединения прямоугольников
427
ным интервалом (вдоль заметающей прямой), который является плоской полосой, заключенной между максимальной орди-
Максимальная ордината ~ для всех прямоугольников, просмотренных к настоящему моменту в данной компоненте
Минимальная ордината среди текущих я/i прямоугольников к
Рис. 8.20. Активная компонента и ее активный интервал. (Заштрихованная полоса будет использоваться здесь и далее для обозначения активных интервалов.)
4J
4J
с
L73F
-4-
(Ь)
(с)
Рис. 8.21. Ситуации, которые могут возникнуть при встрече заметающей прямой с левой стороной, (а)—начинается новая компонента; (Ь)—расширяется одна из уже существующих компонент; (с) — две (или больше) компоненты соединяются. (Показаны активные интервалы после операции вставки.)
натой для всех просмотренных к данному моменту прямоугольников, принадлежащих указанной компоненте, и минимальной ординатой среди активных в этот момент прямоугольников этой компоненты (типичная ситуация показана на рис. 8.20). Активный интервал играет важнейшую роль при определении типа одной из трех возможных ситуаций, которые возникают при
428 Гл. 8. Геометрия прямоугольников
встрече заметающей прямой с левой стороной прямоугольника, как это показано на рис. 8.21.
Когда текущее событие является правой стороной какого-нибудь прямоугольника R, могут возникнуть также три ситуации: (1) R перестает быть активным прямоугольником, не влияя на величину активного интервала (рис. 8.22(a)); или (2) R перестает быть активным прямоугольником, а активный интервал поджимается кверху (рис. 8.22(b): это происходит, только если R является самым нижним из активных прямоугольников данной
Рис. 8.22. Ситуации, которые могут возникнуть при встрече заметающей прямой с правой стороной прямоугольника, (а)—прямоугольник деактиви-руется, не влияя на величину активного интервала; (Ь)—прямоугольник деактивируется, приводя к сужению активного интервала; (с)—компонента завершается. (Вновь активные интервалы показаны после операции уда-
компоненты); или (3) компонента завершается (рис. 8.22(c): это происходит, только если R оставался единственным актив- / ным прямоугольником в данной компоненте).
Для проведения вышеописанных действий статус заметающей прямой реализуется на несколько усложненной структуре данных. Первичная структура организована в форме сбалансированного по высоте дерева Т, листья которого содержат концы активных интервалов. В каждом листе Т, кроме нижнего конца активного интервала, хранится указатель на вторичную структуру, являющуюся также сбалансированным по высоте деревом, в котором хранятся все активные прямоугольники в данной компоненте. Вставки (левых сторон прямоугольников) и удаления (их правых сторон) выполняются следующим образом.
Когда нужно обработать левую сторону [у\,у2], то сначала r/i локализуется в Г, а затем просматривается последовательность листьев до тех пор, пока не найдется также у2. Эта операция исполняется за время 0(\ogN + h), где h — число объ-
