Навигация
Главная
Поиск
Форум
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
Бип из системно... 60692
Invision Power ... 58594
Организация зап... 58569
Модуль Forms 57059
Приложение «Про... 56811
Оператор выбора... 56244
Создание отчето... 55995
Подключение Mic... 55852
ТЕХНОЛОГИИ ДОСТ... 52194
Программируемая... 49487
Пример работы с... 48013
Имитационное мо... 47743
21 ошибка прогр... 42705
Реклама
Сейчас на сайте
Гостей: 11
На сайте нет зарегистрированных пользователей

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

База данных студентов на Delphi + Microsoft SQL Server
Метод половинного деления для нахождения корня уровнения на Turbo Pascal...
Изменения контуров и сортировка в двумерном массиве чисел на Turbo Pasca...

Реклама

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 Комментариев · 8428 Прочтений · Для печати

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


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



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...
Шаблон для новост...

Случайные загрузки
Win-Prolog 3.618
Pass [Исходник на...
Создание Web-сайт...
CodeGear RAD Stud...
Delphi Russian Kn...
Delphi. Учимся на...
Основы программир...
Пример создания W...
Blobs [Исходник н...
Microsoft Press -...
Ehlib
Проигрыватель Mp3
Защита от спама ...
Длинный заголовок...
Программа "AutoRu...
Векторный редакто...
Mass Photo Upload
Основы программир...
Функции Visual Basic
Панель случайной ...

Топ загрузок
Приложение Клие... 100307
Delphi 7 Enterp... 77879
Converter AMR<-... 20021
Borland C++Buil... 10672
GPSS World Stud... 9251
Borland Delphi ... 7658
Turbo Pascal fo... 6884
Visual Studio 2... 4906
Калькулятор [Ис... 3994
FreeSMS v1.3.1 3486
Случайные статьи
Объект PageSetup
Вкладка Configure ...
Выберите то, что м...
DSClient позволяет...
Волоконно-оптическ...
Для каких адресов ...
Время работы прогр...
Аналитические реш...
Основные понятия и...
Создание и конфигу...
Предварительная по...
Файл примера. Поли...
Выбор наилучших ал...
На томе NTFS разре...
Алгоритмы обхода б...
Способен ли сервер...
Пример создания Q-...
Классификация баз ...
Инструмент исследо...
Метаданные. Исполь...
Почему тепловым ст...
Панель случайные ф...
Реализация контейн...
Переходить ли в но...
Тестирование, поис...
Статистика



Друзья сайта
Программы, игры
UP GRADE, ?n bazinului hot?

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