Навигация
Главная
Поиск
Форум
FAQ's
Ссылки
Карта сайта
Чат программистов

Статьи
-Delphi
-C/C++
-Turbo Pascal
-Assembler
-Java/JS
-PHP
-Perl
-DHTML
-Prolog
-GPSS
-Сайтостроительство
-CMS: PHP Fusion
-Инвестирование

Файлы
-Для программистов
-Компонеты для Delphi
-Исходники на Delphi
-Исходники на C/C++
-Книги по Delphi
-Книги по С/С++
-Книги по JAVA/JS
-Книги по Basic/VB/.NET
-Книги по PHP/MySQL
-Книги по Assembler
-PHP Fusion MOD'ы
-by Kest
Professional Download System
Реклама
Услуги

Автоматическое добавление статей на сайты на Wordpress, Joomla, DLE
Заказать продвижение сайта
Программа для рисования блок-схем
Инженерный калькулятор онлайн
Таблица сложения онлайн
Популярные статьи
OpenGL и Delphi... 65535
Форум на вашем ... 65535
HACK F.A.Q 65535
Гостевая книга ... 65535
Содержание сайт... 65535
Вызов хранимых ... 65535
Эмулятор микроп... 65535
Бип из системно... 62592
Организация зап... 59772
Invision Power ... 59429
Приложение «Про... 58658
Оператор выбора... 57776
Модуль Forms 57716
Подключение Mic... 57062
Создание отчето... 56988
ТЕХНОЛОГИИ ДОСТ... 53281
Программируемая... 51052
Пример работы с... 49163
Имитационное мо... 48762
21 ошибка прогр... 43521
Реклама
Сейчас на сайте
Гостей: 7
На сайте нет зарегистрированных пользователей

Пользователей: 13,039
новичок: kaitlynt4yz
Новости
Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ
Delphi, Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog, 3D MAX, Компас 3D
Заказать программу для Windows Mobile, Symbian

Расчет обратной матрицы на Delphi + Пояснительная записка
Моделирование процесса обработки заданий на вычислительном центре на GP...
Моделирование работы ЭВМ на GPSS + Пояснительная записка

Реклама



Подписывайся на YouTube канал о программировании, что бы не пропустить новые видео!

ПОДПИСЫВАЙСЯ на канал о программировании

Q-деревья
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-дереве.
Каждая область разбивается до тех пор, пока не будет содержать не более двух
элементов.
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;


Опубликовал Kest October 23 2009 00:51:47 · 0 Комментариев · 8569 Прочтений · Для печати

• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •


Комментарии
Нет комментариев.
Добавить комментарий
Имя:



smiley smiley smiley smiley smiley smiley smiley smiley smiley
Запретить смайлики в комментариях

Введите проверочный код:* =
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Отлично! Отлично! 100% [1 Голос]
Очень хорошо Очень хорошо 0% [Нет голосов]
Хорошо Хорошо 0% [Нет голосов]
Удовлетворительно Удовлетворительно 0% [Нет голосов]
Плохо Плохо 0% [Нет голосов]
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Поделиться ссылкой
Фолловь меня в Твиттере! • Смотрите канал о путешествияхКак приготовить мидии в тайланде?
Загрузки
Новые загрузки
iChat v.7.0 Final...
iComm v.6.1 - выв...
Visual Studio 200...
CodeGear RAD Stud...
Шаблон для новост...

Случайные загрузки
DFileDeleter
Text3D
45 уроков по дельфи
CoolHints2k
База для Allsubmi...
Blib [Исходник на...
БД сеть компьютер...
isoCanvas (Редакт...
MPTools
Ehlib
Matrix2D
IIIDTrans
Strawberry Prolog...
CS:Source - монит...
Шкрыль А. - Разра...
Использование Lis...
ProLIB18
Функции Visual Basic
Fig [Исходник на ...
Cтатьи Королевств...

Топ загрузок
Приложение Клие... 100333
Delphi 7 Enterp... 79806
Converter AMR<-... 20025
Borland C++Buil... 10823
GPSS World Stud... 9726
Borland Delphi ... 7846
Turbo Pascal fo... 6910
Visual Studio 2... 4926
Калькулятор [Ис... 4123
FreeSMS v1.3.1 3488
Случайные статьи
Где мы находимся?
Получение ресурсов...
Глава 11. Как э...
Группа блоков созд...
Лента
Поддержка многотаб...
Клуб Слотобаза
Сложные термы, или...
RAID уровня 0
Классы и серверы
и режим ядра гаран...
Язык С: проверка т...
данных зоны DNS (т...
10. Эдисон наполни...
Как ответить на во...
Глава 2. Эпизод из...
Общение в чате
Чтобы сократить не...
Метод не занимает ...
К головоломке "зеб...
Прежде чем предост...
RESET (СБРОСИТЬ)
Администратор
Типичные примеры в...
Сколько по времени...
Статистика



Друзья сайта
Программы, игры


Полезно
В какую объединенную сеть входит классовая сеть? Суммирование маршрутов Занимают ли таблицы память маршрутизатора?