Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Задача 0.6 (НЕТРИВИАЛЬНЫЙ КОНТУР ОБЪЕДИНЕНИЯ ПРЯМОУГОЛЬНИКОВ). Дан набор из N изотетичных прямоугольников. Надо найти нетривиальный контур их объединения.
432
Гл. 8. Геометрия прямоугольников
Задача 0.7 (ВНЕШНИЙ КОНТУР ОБЪЕДИНЕНИЯ ПРЯМОУГОЛЬНИКОВ). Дан набор из N изотетичных прямоугольников. Надо построить внешний контур их объединения.
Непосредственно видна справедливость следующей цепочки включений:
Внешний контур s Нетривиальный контур s Нетривиальные цепи.
Важное свойство этих множеств состоит в том, что число дуг в нетривиальных цепях равно 0(N), как это следует из теоремы 8.7:
Теорема 8.7. Общее число дуг в нетривиальных цепях объединения N изотетичных прямоугольников равно 0(N).
Доказательство. Присвоим вершине тип i (i=l, 3), если угол поворота по часовой стрелке между дугами, инцидентными этой вершине (и ориентированными согласно направлению
Вершина mum 1 Вершины типа 3
Рис. 8.26. Типы вершин.
цепи), равен /л/2 (рис. 8.26). Обозначим также через v« число вершин типа i в заданной цепи. Тогда для любой цепи справедливо следующее соотношение:
4 для внутренней (ориентированной против часовой стрелки) цепи, —4 для внешней (ориентированной по часовой стрелке) цепи.
Следовательно, общее число v вершин в цепи (т. е. число дуг) выражается так:
v = v, -f v3 = 2v, ± 4 < 2v, + 4.
Суммируя v по всем нетривиальным цепям, получаем оценку для общего числа дуг t:
t < 2 ? v, + 4 2 i ^ 2 • AN + 4 • 4iV = 24Л7.
8.7. Внешний контур объединения прямоугольников
433
Данная теорема показывает, что если (общий) контур состоит из 0(N2) дуг, то большая их часть принадлежит тривиальным цепям. Поэтому, если необходимо построить именно нетривиальный или внешний контуры, то придется разработать специальные методы, позволяющие избавиться от накладных расходов, создаваемых тривиальными цепями. Однако, прежде чем приступить к решению последней задачи, отметим, что нижней оценкой ее трудоемкости будет ?i (NlogN), поскольку в данной ситуации верны те же самые рассуждения, которые были использованы при доказательстве теоремы 8.5 (в разд. 8.5); действительно, в том доказательстве понятия общего, нетривиального и внешнего контуров совпадали.
V.O-U- ViO---о]
Случаи. 7 Случай Z
Рис. 8.27. Ситуации, возникающие в алгоритме на этапе движения.
Данную задачу вряд ли возможно решить методом плоского заметания, поскольку определить факт тривиальности цепи можно только при окончании процесса заметания (а не в его начале). Недавно был предложен метод [Lipski, Preparata (1981)], осуществляющий «обход» цепей того контура, который следует построить, добавляя по одной дуге на каждом шаге. Ясно, что если обработка каждой дуги потребует O(logjV) времени, то, согласно теоремам 8.5 и 8.7, будет получен оптимальный алгоритм. Приступим к описанию этого метода.
Основной частью процедуры обхода является механизм движения, согласно которому мы отправляемся из текущей вершины v\ (рис. 8.27) и продвигаемся по текущему отрезку 1\ в заданном направлении, причем может возникнуть одна из следующих двух ситуаций.
1. Существует такой отрезок /2, ближайший к v\, который пересекает h и заходит внутрь области, лежащей слева от U. В этом случае делаем левый поворот, т. е. точка пересечения v2 становится текущей вершиной, а /2 — текущим отрезком.
2. Достигнута концевая точка Уз отрезка 1\, совпадающая с концевой точкой отрезка /2 (очевидно, 12 не заходит внутрь области, лежащей слева от /i). В этом случае делаем правый
434
Гл. 8. Геометрия прямоугольников
поворот, т. е. Уз становится текущей вершиной, а 12— текущим отрезком.
Вышеописанный шаг движения можно реализовать путем поиска на двух подходящих геометрических структурах, именуемых горизонтальной и вертикальной картами смежности, которые будут сейчас изложены. Ограничимся горизонтальной картой смежности (ГК.С), поскольку все рассуждения в полной мере применимы к вертикальной карте смежности (ВКС).
Рассмотрим множество V, состоящее из вертикальных отрезков, которые явлются вертикальными сторонами исходных прямоугольников (рис. 8.28). Через каждую концевую точку р
Рис. 8.28. Множество вертикальных отрезков V и результирующая горизонтальная карта смежности.
каждого отрезка из V проведем пару горизонтальных лучей: один вправо и один влево; каждый из этих лучей или заканчивается на ближайшем к р вертикальном отрезке, или если подобного пересечения не существует, то луч продолжается в бесконечность. Таким образом плоскость разбивается на области, две из которых являются полуплоскостями, а все прочие — прямоугольниками, возможно бесконечными в одном или обоих горизонтальных направлениях. Эти области будем называть «обобщенными прямоугольниками». Каждый обобщенный прямоугольник является классом эквивалентности для точек на данной плоскости по отношению к их горизонтальной смежности вертикальным отрезкам (отсюда и название «горизонтальная карта смежности»). Можно простым индуктивным доказательством проверить то, что общее число областей в ГКС не превосходит 3| V|+ 1.
