Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Пусть заданы два интервала: R'= {х[, х'2] и R" = [x", х'2'~\; условие R'fiR" ф 0 эквивалентно одному из следующих взя-
8.8. Пересечения прямоугольников
437
имно исключающих условии:
х\ < х'[ < хг2; (8.2)
*[' < х[ < х". (8.3)
Четыре возможных ситуации взаимного расположения концов интервалов, соответствующих условию R/(]R"?=0, фактически охватываются соотношениями (8.2) и (8.3), что может быть проверено непосредственным образом. Поэтому для проверки пересечения R' и R" достаточно проверить факт попадания или левого конца R' внутрь/?",или левого конца R" внутрь R'.
Указанное свойство одномерной задачи играет важнейную роль при решении следующей задачи:
Задача 0.8 (ОТЧЕТ О ПЕРЕСЕЧЕНИИ ПРЯМОУГОЛЬНИКОВ). Дан на бор из N изотетичных прямоугольников. Надо перечислить все их пересекающиеся пары.
Для решения этой задачи представляется естественным обращение к методу плоского заметания, где точками событий являются, как обычно, абсциссы вертикальных сторон прямоугольников. Статус заметающей исходных прямоугольников упрощения формулировок
Заметающая прямая I
Рис. 8.29. Ситуация, возникающая при достижении заметающей прямой левой стороны прямоугольника R. Показаны только активные прямоугольники.
прямой задается пересечениями с этой заметающей прямой; для назовем вновь прямоугольники, пересеченные заметающей прямой, активными (см. разд. 8.6). Предположим, что в процессе плоского заметания слева направо текущей точкой события стала левая сторона (вновь встреченного) прямоугольника R — [х\, х2] X [у\, у2] ¦ Очевидно, что абсцисса заметающей прямой Х\ (которая совпадает с левым концом х-интервала для R) принадлежит х-интервалам для каждого из активных прямоугольников; поэтому все, что необходимо сделать, состоит в определении того, для каких из активных прямоугольников выполнены условия или (8.2), или (8.3) на их «/-интервалах (рис. 8.29). Кажется, что необходим двукратный поиск: один раз для проверки условия (8.2), а второй для проверки условия (8.3). Двойственная природа этих
438
Гл. 8. Геометрия прямоугольников
двух проверок (одна для определения всех интервалов, содержащих некую точку; другая для определения всех точек, попавших в некий интервал) может навести на мысль об использовании двух разных структур данных и о разработке несколько более сложных алгоритмов [Bentley, Wood (1980); Six, Wood (1980)].
Превосходное решение было получено в результате введения [McCreight (1981); Edelsbrunner (1980)] новой структуры данных, названной Эдельсбруннером деревом интервалов. Хотя возможна и более совершенная динамическая версия интервального дерева, мы ограничимся простым статическим вариантом, пригодным для наших целей.
Если e(i)] обозначает у-интервал для прямоугольника /?('', то пусть (уи г/г, ..., у2ы) обозначает упорядоченную последовательность концов N штук «/-интервалов. (Статическое) дерево интервалов имеет скелетную структуру (именуемую первичной структурой), которая статически зависит от заданной последовательности точек (в нашем случае от последовательности (г/ь г/глг), хотя в ней можно хранить произвольное подмножество (активное подмножество) интервалов, чьи концы принадлежат множеству {уи у2, г/глт}. Тогда дерево интервалов Т на последовательности (уи «/2, • ¦ •, Угы) и множестве интервалов / s {[b[i), е(/)]: i = 1, N}, определяется следующим образом:
1. Корень w дерева Т имеет дискриминант 8 (ay) = (yN 4-+ r/vv—i) /2 и два указателя на (вторичные) списки 3?(w) и 5?(ау). Списки 2?(w) и 3l(w) содержат упорядоченные списки соответственно левых и правых концевых точек тех интервалов из /, которые содержат 8(w). (2? (w) и 91 (w) упорядочены по возрастанию и убыванию соответственно.)
2. Левым поддеревом для w является дерево интервалов на последовательности (г/ь ..., ум) и подмножестве интервалов Ig^I, ординаты правых концов которых не превосходят б (да). Аналогично определяется и правое поддерево для w.
3. Каждый первичный узел в Т считается или «активным», или «неактивным». Узел активен, если его вторичные списки непусты или если в обоих его поддеревьях есть активные узлы.
Статическое дерево интервалов обладает рядом интересных свойств, следующих прямо из вышеизложенного определения:
(1) Первичная структура Т является сбалансированным двоичным деревом, листья которого связаны с величинами ?/ь • • •, y2N, и прохождение по Т во внутреннем порядке дает упорядоченную последовательность (уь y2N).
(2) На вторичных списках 3?(v) и 91 (v) для нелистового первичного узла v должны быть определены операции вставки
8.8. Пересечения прямоугольников
439
и удаления элементов. Эти списки удобно реализовать как сбалансированные по высоте или весу деревья.
(3) Активные узлы можно однозначно связать в структуру, представляющую собой двоичное дерево д~, каждая дуга которого соответствует пути (или его части), исходящему из корня Т. Поэтому каждому первичному узлу v припишем два указателя: ЛУ (левый указатель) и ПУ (правый указатель), используемые для реализации дерева Т. Если узел v неактивен, то ЛУ[и] = Л и ПУ[а] = Л; однако если v активен, то ЛУ^]Ф ф Л только тогда, когда существуют активные узлы в левом
