Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
8.6. Замыкание объединения прямоугольников
429
единенных активных интервалов (рис. 8.21(c)); у2 вставляется также и во вторичную структуру, и если h ^ 2, то соответствующие вторичные структуры сцепляются (как сцепляемые очереди). Затраты на конкатенацию вторичных структур за время работы алгоритма легко оценить, если О (log Л7) операций, затраченных на сцепление двух подобных структур А\ и А2, отнести на счет крайнего правого активного прямоугольника Л1; а поскольку на каждый прямоугольник такие затраты могут относиться не более одного раза, то верхняя оценка затрат на сцепление равна 0(N\ogN).
Когда нужно обработать правую сторону [уи у2] вновь, сначала находим у\ в активном интервале (в первичной структуре Т). Затем элемент у\ находится также в соответствующей вторичной структуре и удаляется из нее, а если он совпадает с минимальным элементом этой вторичной структуры, то корректируется и значение нижнего конца активного интервала (рис. 8.22(b)). Наконец, если у\ является единственным элементом вторичной структуры, то соответствующий активный интервал удаляется также из первичной структуры. Очевидно, что обработку любой правой стороны можно выполнить за время O(logyV).
Плоское заметание справа налево, при котором строится ЮЗ(СВ(/Г)), проводится аналогично, поэтому справедлива
Теорема 8.6. СВЮЗ-замыкание объединения N изотетичных прямоугольников можно построить, затратив оптимальные время Q(N\ogN) и память 9 (М).
Доказательство (набросок). Действительно, после предварительной сортировки абсцисс сторон прямоугольников обработка этих 2N сторон займет также время 0(N\ogN), как показано выше. Структуры данных для этой работы занимают O(N) памяти. Эти оценки оптимальны, поскольку задачу об уникальности элементов можно легко преобразовать в задачу о замыкании объединения прямоугольников.
Замечание. Вышеизложенный метод легко приспособить для вычисления связных компонент множества прямоугольников с сохранением таких же оценок по времени и памяти1). Действительно, легко убедиться, что все отличие состоит в замене (единственного) активного интервала для каждой компоненты (как описано выше) набором непересекающихся интервалов, представляющих собой сечения, образованные заметающей прямой и активными прямоугольниками из этой компоненты.
') См. также [Edelsbrunner, Van Leeuwen, Ottman, Wood (1981)1.
430
Гл. 8. Геометрия прямоугольников
8.7. Внешний контур объединения прямоугольников
В предыдущем разделе было показано, как один основной метод — плоское заметание — можно приспособить для решения множества разных задач, связанных с объединением изотетичных прямоугольников, таких как вычисление их площади, периметра, замыкания и контура (задачи 0.1, 0.3, 0.4 и 0.5). Как указывалось раньше (см. разд. 8.5), контур объединения N прямоугольников может иметь б (Л/'2) ребер, однако это неверно для подмножества контура, задаваемого следующим определением:
Определение 8.4. Внешним контуром объединения изотетичных прямоугольников F называется граница между F и бесконечной областью плоскости.
Покажем теперь, что внешний контур имеет 0(N) ребер. Этот результат устанавливается легко, если использовать два интересных супермножества внешнего контура, первое из которых вводится следующим определением:
Определение 8.5. Нетривиальным контуром объединения изотетичных прямоугольников F называется множество таких контурных циклов, каждый из которых содержит по меньшей мере одну вершину какого-нибудь из исходных прямоугольников.
Примеры этих трех объектов — контура, нетривиального контура и внешнего контура —даны на рис. 8.23. Из этого рисунка непосредственно видно, что внешний контур является подмножеством нетривиального контура.
(а) (Ь) (с)
Рис. 8.23. Примеры: (а) — контура, (Ь) — нетривиального контура и (с) — внешнего контура для объединения прямоугольников.
Для дальнейшего изложения будет удобно считать каждое ребро состоящим из двух дуг, ориентированных в противоположных направлениях и лежащих по разные стороны от исходного ребра, как показано на рис. 8.24. Ребра прямоугольников Ri, RN разбивают плоскость на области, одна из которых бесконечна. После введения вспомогательных дуг границы всех
8.7. Внешний контур объединения прямоугольников 431
областей этого разбиения порождают набор ориентированных цепей, состоящих из дуг; подобная цепь называется внешней или внутренней в зависимости от того, будет ли она ориентирована по часовой стрелке или против. Дуга в цепи называется
Рис. 8.24. Соглашения относительно направлений объединяющих дуг для заданного ребра.
концевой, если она содержит концевую точку того исходного отрезка (стороны прямоугольника), которому она принадлежит. Цепь называется нетривиальной или тривиальной в зависимости от того, содержит она или нет концевую дугу. Множество
Рис. 8.25. Нетривиальные цепи для объединения прямоугольников, изображенного на рис. 8.23.
нетривиальных цепей для примера с рис. 8.23 проиллюстрировано на рис. 8.25. Теперь можно поставить следующие задачи:
