Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
94
Гл. 2. Геометрический поиск
В последующем обсуждении различных подходов к d-мерно-му региональному поиску прежде всего будем рассматривать простейший случай (т. е. d = 2) для выявления таких существенных черт каждого метода, которые свободны от бремени размерности. После достижения указанной цели мы будем стремиться там, где это уместно, к обобщению на произвольное число измерений.
2.3.2. Метод многомерного двоичного дерева (k-D-дерева)
Мы только что видели чрезвычайную важность дихотомии при разработке оптимального метода для одномерного регионального поиска. Поэтому естественно попытаться обобщить дихотомию на двумерный случай, где файл является набором из N точек, лежащих на плоскости (х, у). То, что делается при дихотомии, есть не что иное, как последовательное разрезание региона (неважно, конечного или бесконечного) на две части. В случае двух измерений всю плоскость можно считать бесконечным прямоугольником, который будет разрезан сначала на две полуплоскости прямой, параллельной одной из осей, скажем оси у. Затем каждая из этих полуплоскостей может разрезаться еще раз прямой, параллельной оси х, и т. д., меняя на каждом шаге направление разрезающей линии, например от х к у. Как выбирать разрезающие линии? В точном соответствии с тем же принципом, который используется при обычной дихотомии, т. е. руководствуясь принципом получения приблизительно равного числа элементов (точек) по каждую сторону от разреза. Таким образом мы пришли к правомерному обобщению дихотомии и, более того, к основной идее метода многомерного двоичного дерева [Bentley (1975)].
Более строго, назовем (обобщенным) прямоугольником такую область на плоскости, которая определена декартовым произведением [х\, *2]Х0/ь №>1 ^-интервала \Х\,х^ и у-интервала [1/1,1/2]. включая предельные случаи, когда, в любой комбинации допускается: х\ = —со, х2 = оо, у\ = —со, у2 = со. Поэтому мы будем считать прямоугольниками также неограниченные (с одной или двух сторон) полосы, любой квадрант, или даже всю плоскость. - '"'"П
Процесс разбиения 5 путем разрезания плоскости лучше всего иллюстрировать в сочетании с построением двумерного двоичного дерева Т. С каждым v узлом Т мы неявно связываем прямоугольник Ш(v) (он определен выше) и подмножество S(v) точек, лежащих внутри 52(f); явно же, т.е. как фактические параметры этой структуры данных, свяжем с v одну избранную точку P(v) из S(v) и «секущую прямую»t(v),проходящую через P(v) и параллельную одной из координатных осей.
2.3. Задачи регионального поиска 95
Этот процесс начинается с определения корня Т. С ^{корень) соотносится вся плоскость, и полагается, что 5 (корень) = S; затем определяется точка peS, такая что х{р) — медиана множества абсцисс точек из S (корень), и полагается, что Р(корень) = р, а с /(корень) соотносится прямая с уравнением х = х(р). Точка р разбивает 5 на два множества приблизительно равной мощности, назначенных потомкам корня. Процесс
(а) (Ы
Рис. 2.27. Иллюстрация метода поиска с помощью двумерного двоичного дерева. Разбиение плоскости (а) моделируется деревом (Ь). Поиск начинается с проведения вертикали через Р6. На рис. (Ь) -приняты следующие графические обозначения: круглые узлы соответствуют вертик^лм*"м резам, квадратные — горизонтальным, точки — листьям дерева.
дробления прекращается, когда обнаружен прямоуольник, не содержащий внутри точек; соответствующий ему узел является листом дерева Т.
Данный метод проиллюстрирован на примере с рис. 2.27 для множества из N = 11 точек. Узлы трех разных типов обозначены различными графическими символами: кружками — нелистовые узлы с вертикальной линией разреза, квадратами — нелистовые узлы с горизонтальной линией разреза, точками — листья. Такая структура данных часто называется 2-D-depeeoM (аббревиатура выражения «двумерное двоичное дерево поиска»).
Изучим теперь использование структуры данных типа 2-?>-дерева для регионального поиска. Алгоритмической схемой будет метод «разделяй и властвуй» в чистом виде. Действительно, рассмотрим взаимное расположение прямоугольной области Я.(и), связанной с v узлом Т, и некоего прямоугольного региона D такого, что Я(v) и D имеют непустое пересечение. Область Я(v) разрезана на два прямоугольника R\ и R2 прямой l(v), проходящей через P(v). Если D Г) &(v) полностью содержится
Гл. 2. Геометрический поиск
в Ri (i = 1, 2), то поиск продолжается с единственной парой типа (область, регион), а именно с {Ri, D). Если же область D Г] &l(v) разрезана прямой l(v), то l(v) имеет непустое пересечение с О, а значит, D может содерж^т^~Р^{хгу. Поэтому сначала проверим, находится ли P(v) внутри D, и если да, то поместим эту точку в выбираемое множество; затем продолжим поиск с двумя парами типа (область, регион), а именно с (R\, D) и (R2,D). Этот процесс поиска прекращается при достижении любого листа.
Более строго любой узел v дерева Т характеризуется тройкой параметров {P(v), t(v), M(v)). Точка P(v) уже была определена. Два других параметра вместе определяют прямую l{v), а именно t(v) определяет горизонтальность или вертикальность l{v); в первом случае l(v) — это прямая у = M(v) '), во втором случае — это прямая x = M(v)2). Данный алгоритм накапливает выбираемые точки в списке U — внешнем по отношению к процедуре и первоначально пустом. Обозначая через D = = 1хи x2]~X[yi, У2] запросный регион, получаем, что поиск на дереве Т осуществляется вызовом процедуры ПОИСК(ко-рень(Г),?>), имеющей следующее описание:
