Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Горизонтальная карта смежности является просто частным случаем разбиения плоскости, порожденного укладкой пленарного графа. Если предположить, что текущий отрезок 1\ горизонтален (рис. 8.27), то локализация текущей вершины v\ в одной из областей исходной карты (т. е. определение того обобщенного прямоугольника, который содержит v\) означает опре-
(Ъ)
8.7. Внешний контур объединения прямоугольников
435
деление вертикальных сторон этой области. Легко убедиться, что это все, что требуется для реализации шага движения. Действительно, предположим, что v\ — (хи у\), a h лежит на прямой у = yi в интервале [хихъ\. Локализуем точку (хиу\) в ГК.С и получаем абсциссу х2 для ближайшего вертикального отрезка, лежащего справа от (х\,у\). Если х2 ^ х3, то надо сделать левый поворот (случай 1); если х2 > х3, то надо сделать правый поворот (случай 2). Три оставшихся случая расположения текущего отрезка (слева, сверху и снизу от текущей вершины) обрабатываются совершенно аналогичным образом. Поэтому добавка одной дуги к нетривиальной цепи занимает столько же времени, сколько одно обращение к любой из карт смежности.
Для реализации процедуры обращения к карте смежности (т. е. для локализации точки на плоскости) можно прибегнуть к одному из многих методов поиска, описанных в разд. 2.2, и с оценкой по времени О (log Л'). Особенно удобен для данной ситуации так называемый метод трапеций (на основе медиан) (разд. 2.2.2.4), причем благодаря природе исходной плоской карты (определенной множеством параллельных отрезков) указанные трапеции становятся прямоугольниками. Для O(N) точек (как в нашем случае, поскольку число вершин исходных изотетичных прямоугольников равно 4N) данный метод тратит на поиск О (log Л') времени, используя структуру данных (двоичное дерево поиска), которую можно построить за время О (NlogN). Нежелательным аспектом этого, в остальном весьма простого метода является то, что в худшем случае он требует О (NlogN) памяти вместо Q(N). Однако вероятностный анализ [Bilardi, Preparata (1982)], надежно базирующийся на большом экспериментальном материале, показал, что для широкого класса гипотез относительно статистического распределения отрезков средний объем необходимой памяти равен Q(N) с очень малой, практически приемлемой мультипликативной константой (равной примерно 6).
Нетривиальный контур (и, следовательно, внешний контур) можно получить, систематически построив множество всех нетривиальных цепей, а затем удалив нежелательные его элементы. Порождение нетривиальных цепей можно осуществить в результате применения вышеописанного шага движения к вершине прямоугольника и той дуге, которая выходит из нее и направлена вовне прямоугольника. Тем самым каждая вершина прямоугольника становится «ростком цепи». Вначале все вершины занесены в память (массив) и помечены. Они извлекаются поочередно из указанного массива для генерации всех нетривиальных цепей, а этот процесс прекращается, когда массив становится пустым. Поскольку в нетривиальных цепях
436
Гл. 8. Геометрия прямоугольников
имеется О (Л/) дуг, а построение одной такой дуги можно проделать за время О (log Л7), то все множество нетривиальных цепей можно построить за время О (Л7 log Л7), включая сюда и время предварительной обработки для построения деревьев поиска на картах смежности.
Для завершения построения внешнего контура необходимо удалить те цепи, которые не отделяют F от его внешности. Чтобы отличить нетривиальные цепи, которые принадлежат внешнему контуру, от тех, которые не принадлежат ему, можно создать процедуру плоского заметания, требующую О (Л7 log Л7) времени (см. упр. 1 в конце данной главы).
Теорема 8.8. Нетривиальный и внешний контуры объединения из N изотетичных прямоугольников можно построить за оптимальное время 6 (Л7 log N), затратив в худшем случае O(NlogN) памяти.
8.8. Пересечения прямоугольников и связанные с этим задачи
В предыдущих разделах обсуждались методы вычисления некоторых глобальных свойств множества изотетичных прямоугольников, таких как мера, периметр и т. п. В настоящем разделе будет, напротив, рассматриваться задача вычисления двух отношений, которые естественным образом определены на множестве прямоугольников. Эти два отношения «пересечение» и «включение» (или, как иногда говорят, «охват») рассматриваются по отдельности в следующих разделах.
8.8.1. Пересечения прямоугольников
Два изотетичных прямоугольника пересекаются тогда и только тогда, когда у них есть по крайней мере одна общая точка. Простейшим примером является случай одного измерения, где «прямоугольники» — это интервалы на прямой линии. Поскольку d-мерный прямоугольник является декартовым произведением d интервалов, каждый из которых определен на соответствующей координатной оси, то два d-мерных прямоугольника пересекаются тогда и только тогда, когда пересекаются их проекции (два интервала) на ось х,- для всех /' = 1, 2, ..., d. Итак, очевидно, что одномерный случай играет фундаментальную роль, поэтому он будет изучен прежде всего.
