Эту операцию можно выполнить намного быстрее при помощи квадродерева. Начнем с корневого узла. При каждой проверке квадродерева определяем, какой из квадрантов содержит точку, которую выбрал пользователь. Затем спустимся вниз по дереву к соответствующему дочернему узлу. Если пользователь выбрал верхний правый угол области узла, нужно спуститься к северо‑восточному потомку. Продолжим движение вниз по дереву, пока не дойдем до листа, который содержит выбранную пользователем точку.
Функция LocateLeaf класса QtreeNode использует этот подход для поиска листа дерева, который содержит выбранную точку. Программа может вызвать эту функцию в строке Set the_leaf = Root.LocateLeaf(X, Y, Gxmin, Gxmax, Gymax), где Gxmin, Gxmax, Gymin, Gymax — это границы представленной деревом области.
Public Function LocateLeaf (X As Single, Y As Single, _
xmin As Single, xmax As Single, ymin As Single, ymax As Single) _
As QtreeNode
Dim xmid As Single
Dim ymid As Single
Dim node As QtreeNode
If NWchild Is Nothing Then
' Узел не имеет потомков. Искомый узел найден.
Set LocateLeaf = Me
Exit Function
End If
' Найти соответстующего потомка.
xmid = (xmax + xmin) / 2
ymid = (ymax + ymin) / 2
If X <= xmid Then
If Y <= ymid Then
Set LocateLeaf = NWchild.LocateLeaf( _
X, Y, xmin, xmid, ymin, ymid)
Else
Set LocateLeaf = SWchild.LocateLeaf _
X, Y, xmin, xmid, ymid, ymax)
End If
Else
If Y <= ymid Then
Set LocateLeaf = NEchild.LocateLeaf( _
X, Y, xmid, xmax, ymin, ymid)
Else
Set LocateLeaf = SEchild.LocateLeaf( _
X, Y, xmid, xmax, ymid, ymax)
End If
End If
End Function
После нахождения листа, который содержит точку, проверяем населенные пункты в листе, чтобы найти, который из них ближе всего от выбранной точки. Это делается при помощи процедуры NearPointInLeaf.
Public Sub NearPointInLeaf (X As Single, Y As Single, _
best_item As QtreeItem, best_dist As Single, comparisons As Long)
Dim new_item As QtreeItem
Dim Dx As Single
Dim Dy As Single
Dim new_dist As Single
' Начнем с заведомо плохого решения.
best_dist = 10000000
Set best_item = Nothing
' Остановиться если лист не содержит элементов.
If Items.Count < 1 Then Exit Sub
For Each new_item In Items
comparisons = comparisons + 1
Dx = new_item.X - X
Dy = new_item.Y - Y
new_dist =Dx * Dx + Dy * Dy
If best_dist > new_dist Then
best_dist = new_dist
Set best_item = new_item
End If
Next new_item
End Sub
======147-148
Элемент, который находит процедура NearPointLeaf, обычно и есть элемент, который пользователь пытался выбрать. Тем не менее, если элемент находится вблизи границы между двумя узлами, может оказаться, что ближайший к выбранной точке элемент находится в другом узле.
Предположим, что Dmin — это расстояние между выбранной пользователем точкой и ближайшим из найденных до сих пор населенных пунктов. Если Dmin меньше, чем расстояние от выбранной точки до края листа, то поиск закончен. Населенный пункт находится при этом слишком далеко от края листа, чтобы в каком‑либо другом листе мог существовать пункт, расположенный ближе к заданной точке.
В противном случае нужно снова начать с корня и двигаться по дереву, проверяя все узлы квадродеревьев, которые находятся на расстоянии меньше, чем Dmin от заданной точки. Если найдутся элементы, которые расположены ближе, изменим значение Dmin и продолжим поиск. После завершения проверки ближайших к точке листьев, нужный элемент будет найден. Подпрограмма CheckNearByLeaves использует этот подход для завершения поиска.
Public Sub CheckNearbyLeaves(exclude As QtreeNode, _
X As Single, Y As Single, best_item As QtreeItem, _
best_dist As Single, comparisons As Long, _
xmin As Single, xmax As Single, ymin As Single, ymax As Single)
Dim xmid As Single
Dim ymid As Single
Dim new_dist As Single
Dim new_item As QtreeItem
' Если это лист, который мы должны исключить,
' ничего не делать.
If Me Is exclude Then Exit Sub
' Если это лист, проверить его.
If SWchild Is Nothing Then
NearPointInLeaf X, Y, new_item, new_dist, comparisons
If best_dist > new_dist Then
best_dist = new_dist
Set best_item = new_item
End If
Exit Sub
End If
' Найти потомков, которые удалены не больше, чем на best_dist
' от выбранной точки.
xmid = (xmax + xmin) / 2
ymid = (ymax + ymin) / 2
If X - Sqr(best_dist) <= xmid Then
' Продолжаем с потомками на западе.
If Y - Sqr(best_dist) <= ymid Then
' Проверить северо-западного потомка.
NWchild.CheckNearbyLeaves _
exclude, X, Y, best_item, _
best_dist, comparisons, _
xmin, xmid, ymin, ymid
End If
If Y + Sqr(best_dist) > ymid Then
' Проверить юго-западного потомка.
SWchiId.CheckNearbyLeaves _
exclude, X, Y, best_item, _
best_dist, comparisons, _
xmin, xmid, ymid, ymax
End If
End If
If X + Sqr(best_dist) > xmid Then
' Продолжить с потомками на востоке.
If Y - Sqr(best_dist) <= ymid Then
' Проверить северо-восточного потомка.
NEchild.CheckNearbyLeaves _
exclude, X, Y, best_item, _
best_dist, comparisons, _
xmid, xmax, ymin, ymid
End If
If Y + Sqr(best_dist) > ymid Then
' Проверить юговосточного потомка.
SEchild.CheckNearbyLeaves _
exclude, X, Y, best_item, _
best_dist, comparisons, _
xmid, xmax, ymid, ymax
End If
End If
End Sub
=====149-150
Подпрограмма FindPoint использует подпрограммы LocateLeaf, NearPointInLeaf, и CheckNearbyLeaves, из класса QtreeNode для быстрого поиска элемента в квадродереве.
Function FindPoint(X As Single, Y As Single, comparisons As Long) _ As QtreeItem
Dim leaf As QtreeNode
Dim best_item As QtreeItem
Dim best_dist As Single
' Определить, в каком листе находится точка.
Set leaf = Root.LocateLeaf( _
X, Y, Gxmin, Gxmax, Gymin, Gymax)
' Найти ближайшую точку в листе.
leaf.NearPointInLeaf _
X, Y, best_item, best_dist, comparisons
' Проверить соседние листья.
Root.CheckNearbyLeaves _
leaf, X, Y, best_item, best_dist, _
comparisons, Gxmin, Gxmax, Gymin, Gymax
Set FindPoint = best_item
End Function
Программа Qtree использует квадродерево. При старте программа запрашивает число элементов данных, которое она должна создать, затем она создает элементы и рисует их в виде точек. Задавайте вначале небольшое (около 1000) число элементов, пока вы не определите, насколько быстро ваш компьютер может создавать элементы.
Интересно наблюдать квадродеревья, элементы которых распределены неравномерно, поэтому программа выбирает точки при помощи функции странного аттрактора (strange attractor) из теории хаоса (chaos theory). Хотя кажется, что элементы следуют в случайном порядке, они образуют интересные кластеры.
При выборе какой‑либо точки на форме при помощи мыши, программа Qtree находит ближайший к ней элемент. Она подсвечивает этот элемент и выводит число проверенных при его поиске элементов.
В меню Options (Опции) программы можно задать, должна ли программа использовать квадродеревья или нет. Если поставить галочку в пункте Use Quadtree (Использовать квадродерево), то программа выводит на экран квадродерево и использует его для поиска элементов. Если этот пункт не выбран, программа не отображает квадродерево и находит нужные элементы путем перебора.
Программа проверяет намного меньшее число элементов и работает намного быстрее при использовании квадродерева. Если этот эффект не слишком заметен на вашем компьютере, запустите программу, задав при старте 10.000 или 20.000 входных элементов. Вы заметите разницу даже на компьютере с процессором Pentium с тактовой частотой 90 МГц.
На рис. 6.26 показано окно программа Qtree на котором изображено 10.000 элементов. Маленький прямоугольник в верхнем правом углу обозначает выбранный элемент. Метка в верхнем левом углу показывает, что программа проверила всего 40 из 10.000 элементов перед тем, как найти нужный.
Интересно поэкспериментировать с программой Qtree, изменяя значение MAX_PER_NODE, определенное в разделе Declarations класса QtreeNode. Это максимальное число элементов, которые могут поместиться в узле квадродерева без его разбиения. Программа обычно использует значение MAX_PER_NODE = 100.
======151
@Рис. 6.26. Программа Qtree
Если вы уменьшите это число, например, до 10, то в каждом узле будет находиться меньше элементов, поэтому программа будет проверять меньше элементов, чтобы найти ближайший к выбранной вами точке. Поиск будет выполняться быстрее. С другой стороны, программе придется создать намного больше узлов квадродерева, поэтому она займет больше памяти.
Наоборот, если вы увеличите MAX_PER_NODE до 1000, программа создаст намного меньше узлов. При этом потребуется больше времени на поиск элементов, но дерево будет меньше, и займет меньше памяти.
Это пример компромисса между временем и пространством. Использование большего числа узлов квадродерева ускоряет поиск, но занимает больше памяти. В этом примере, при значении переменной MAX_PER_NODE примерно равном 100, достигается равновесие между скоростью и использованием памяти. Для других приложений вам может потребоваться поэкспериментировать с различными значениями переменной MAX_PER_NODE, чтобы найти оптимальное.
Программа Qtree использует большое число классов и коллекций. Каждый внутренний узел квадродерева содержит четыре ссылки на дочерние узлы. Листья включают большие коллекции, в которых находятся элементы узла. Все эти объекты и коллекции замедляют работу программы, если она содержит большое числе элементов. Создание объектов отнимает много времени и памяти. Если программа создает множество объектов, она может начать обращаться к файлу подкачки, что сильно замедлит ее работу.
К сожалению, выигрыш от использования квадродеревьев будет максимальным, если программа содержит много элементов. Чтобы улучшить производительность больших приложений, вы можете использовать методы работы с псевдоуказателями, описанные во 2 главе.
=====152
Программа Qtree2 создает квадродерево при помощи псевдоуказателей. Узлы и элементы находятся в массивах определенных пользователем структур данных. В качестве указателей, эта программа использует индексы массивов вместо ссылок на объекты. В одном из тестов на компьютере с процессором Pentium с тактовой частотой 90 МГц, программе Qtree потребовалось 25 секунд для построения квадродерева, содержащего 30.000 элементов. Программе Qtree2 понадобилось всего 3 секунды для создания того же дерева.
Восьмеричные деревья (octtrees) аналогичны квадродеревьям, но они разбивают область не двумерного, а трехмерного пространства. Восьмеричные деревья содержат не четыре потомка, как квадродеревья, а восемь, разбивая объем области на восемь частей — верхнюю северо‑западную, нижнюю северо‑западную, верхнюю северо‑восточную, нижнюю северо‑восточную и так далее.
Восьмеричные деревья полезны при работе с объектами, расположенными в пространстве. Например, робот может использовать восьмеричное дерево для отслеживания близлежащих объектов. Программа рейтрейсинга может использовать восьмеричное дерево для того, чтобы быстро оценить, проходит ли луч поблизости от объекта перед тем, как начать медленный процесс вычислений точного пересечения объекта и луча.