Q-дерево (quadtree) описывает пространственные отношения между элемен-
тами в пределах какой-либо ограниченной площади. Например, область может
быть картой, а элементы будут обозначать расположение домов или предприятий
на ней.
Каждый узел в Q-дереве является частью общей области, представленной дан-
ным деревом. Каждый узел, который не является листом, имеет четыре дочерних,
узла которые соответствуют северо-западному, северо-восточному, юго-восточно-
му и юго-западному квадранту области узла. Лист может хранить элементы в свя-
занном списке. Следующий код показывает ключевые части объявления класса
TQtreeNode.
type
NorthOrSouth = (North,South);
EastOrWest = (East,West);
TPointArray = array [1..MAX_QTREE_NODES] of TPoint;
PPointArray = ^TPointArray;
TQtreeNode = class(TObject)
private
public
Children : array [NorthOrSouth, EastOrWest] of TQtreeNode;
Xmin, Xmax ,Ymin ,Ymax : Integer;
Pts : PPointArray; // Элементы
// данных.
NumPts : Integer;
:
end;
Чтобы построить Q-дерево, разместите все элементы в корневом узле. Затем
определите, содержит ли данный узел достаточно элементов, которые можно еще
поделить на несколько других. Если это так, создайте четыре дочерних записи для
этого узла. Распределите элементы среди этих четырех потомков в соответствии
с позициями элементов в пределах четырех квадрантов исходной области. Потом
рекурсивно проверьте эти четыре дочерних записи, чтобы отследить, можно ли их
еще разделить. Продолжайте разбивать узлы до тех пор, пока каждый лист не бу-
дет содержать не более определенного числа элементов.
На рис. 6.25 показано несколько элементов данных, размещенных в Q-дереве.
Каждая область разбивается до тех пор, пока не будет содержать не более двух
элементов.
Рис. 6.25. Q-дерево
Q-деревья используются для поиска близлежащих объектов. Предположим,
имеется программа, которая рисует карту со многими участками. Когда пользова-
тель щелкает мышью по карте, программа должна найти ближайший к выбранной
точке населенный пункт. Система может перебрать весь список участков, прове-
ряя для каждого расстояние от заданной точки. Если имеется N участков, то это
алгоритм сложности O(N).
При помощи Q-дерева эту операцию можно выполнить намного быстрее. Нач-
ните с корневого узла. При каждой проверке Q-дерева определяйте, какой из квад-
рантов узла содержит точку, где пользователь щелкнул мышью. Затем двигайтесь
вниз к соответствующему дочернему узлу. Если бы пользователь щелкнул в пра-
вом верхнем углу области узла, вы бы перешли к северо-восточному дочернему
узлу. Двигайтесь вниз, пока не достигнете листа, где находится точка, которую
выбрал пользователь.
Функция LocateLeaf класса TQtreeNode использует этот метод для обнару-
жения листа, который содержит данную точку. Программа вызывает эту функцию
в строке the_leaf:=Root.LocateLeaf(X,Y):
// Какой лист содержит точку.
function TQtreeNode.LocateLeaf(X, У : Integer) : TQtreeNode;
var
xmid, ymid : Integer;
ns : NorthOrSouth;
ew : EastOrWest;
begin
if (Children[North,West] = nil) then
begin
// У данного узла нет дочерних. Он должен быть листом.
Result := Self;
exit;
end;
// Нахождение соответствующего дочернего узла.
xmid := (Xmax+Xmin) div 2;
ymid := (Ymax+Ymin) div 2;
if (Y<=ymid) then
ns := North
else
ns := South;
if (X<=xmid) then
ew := West
else
ew := East;
Result := Children[ns,ew].LocateLeaf(X,Y) ;
end;
Когда будет найден лист, содержащий искомую точку, рассмотрите участки в пре-
делах этого листа, чтобы найти самый близкий элемент. Это делается при помощи
процедуры NearPointlnLeaf:
// Возвращает индекс ближайшей к заданным координатам точки
// в данном узле.
procedure TQtreeNode.NearPointlnLeaf(X, Y: Integer;
var best_i, best_dist2 : Integer; var comp : Longint);
var
I : Longint;
dist2, dx, dy : Integer;
begin
best_dist2 := 32767;
best_I := 0;
for I := 1 to NumPts do
begin
dx := X-Pts^[i].X;
dy := Y-PtS^[i].Y;
dist2 := dx*dx+dy*dy;
if (best_dist2>dist2) then
begin
best_I := i;
best_dist2 := dist2;
end;
end;
comp := comp+NumPts;
end;
Элемент, найденный функцией NearPointlnLeaf, обычно является именно
тем элементом, который пытался выбрать пользователь. Но если точка располо-
жена близко к границе между двумя листами, то ближайшим к выбранной точке
пунктом может оказаться точка другого узла.
Предположим, что Droin - это расстояние от выбранной точки до самого близ-
кого участка, найденного на данный момент. Если Dmin меньше, чем расстояние от
точки до края листа, то искомый элемент найден. Населенный пункт находится
при этом слишком далеко от края листа, чтобы в каком-либо другом листе мог су-
ществовать пункт, расположенный ближе к заданной точке.
В противном случае вернитесь к корневому узлу и двигайтесь по дереву, изу-
чая все узлы, которые находятся в пределах расстояния Dmin от выбранной точки.
Если вы нашли несколько ближайших к точке элементов, повторите операцию для
меньшего значения Dmin. Когда закончится проверка ближайших к точке листьев,
нужный элемент будет найден. Процедура CheckNearbyLeaves использует этот
метод для завершения поиска.
// Исследование ближайших узлов. Нет ли среди них лучшей точки?
procedure TQtreeNode.CheckNearbyLeaves(exclude : TQtreeNode;
var best_leaf : TQtreeNode; X, Y : Integer;
var best_i, best_dist2 : Integer; var comp : Longint);
var
xmid, ymid, i, dist2, best_dist : Integer;
begin
// Если лист исключается, то ничего не происходит.
if (exclude=Self) then exit;
// Если это лист, то рассматриваются ближайшие узлы.
if (Children[North,West] = nil) then
begin
NearPointlnLeaf(X,Y,i,dist2,comp);
if (best_dist2>dist2) then
begin
best_dlst2 := dist2;
best_leaf := Self;
best_i := i;
end;
end else begin
// Рассматриваются дочерние узлы, которые лежат в пределах
// best_dist искомой точки.
xmid := (Xmax+Xmin) div 2;
ymid := (Ymax+Ymin) div 2;
best_dist :=Round(Sqrt(best_dist2)+0.5);
if (X-best_dist<=xmid) then
begin
// Западный дочерний узел может быть достаточно близок.
// Достаточно ли близок северо-западный дочерний узел?
if (Y-best_dist<=ymid) Then
Children[North,West].CheckNearbyLeaves(
exclude, best_leaf, X, Y, best_i, best_dis2, comp) ;
// Достаточно ли близок юго-западный дочерний узел?
if (Y+best_dist>ymid) Then
Children[South,West].CheckNearbyLeaves(
exclude,best_leaf,X,Y,best_i,best_dist2,comp) ;
end; // Конец проверки западного дочернего узла.
if. (X+bestf_dist>xmid) then
begin
// Восточный дочерний узел может быть достаточно близок.
// Достаточно ли близок северо-восточный дочерний узел?
if (Y-best_dist<=ymid) Then
Children[North,East].CheckNearbyLeaves(
exclude,best_leaf,X,Y,best_i,best_dist2,comp);
// Достаточно ли близок юго-восточный дочерний узел?
if (Y+best_dist>ymid) Then
ChiIdren[South,East].CheckNearbyLeaves(
exclude,best_leaf,X,Y,best_i,best_dist2,comp);
end; // Конец проверки восточного дочернего узла.
end; // Конец if лист ... else проверка дочерних
end;
Процедура FindPoint использует процедуры LocateLeaf, NearPointln-
Leaf и CheckNearbyLeaves из класса QtreeNode, чтобы быстро определить
положение точки в Q-дереве.
// Нахождение ближайшей точки к точке с заданными координатами.
procedure TQtreeNode.FindPoint(var X, Y : Integer
var comp : Longint) ;
var
best_dist2, best_i : Integer;
leaf : TQtreeNode;
begin
// Какой лист содержит точку.
leaf := LocateLeaf(X,Y) ;
// Нахождение ближайшей точки в пределах листа.
comp := 0;
leaf.NearPointlnLeaf(X,Y,best_i,best_dist2,comp);
// Проверка ближайших листов на наличие ближайшей точки.
CheckNearbyLeaves(leaf,leaf,X,Y,best_i,best_dist2,comp);
X := leaf.Pts^[best_i].X;
Y := leaf.Pts^[best_i].Y;
end;
|
Главная
Каталог файлов
