Структура данных программного комплекса Q-дерево (стр. 2 из 4)

· Предусловия

Указатель на дерево не должен быть пустым

· Локальные переменные

- CurNode – текущий квадрант (тип PNode);

- ParentNode – родительский узел листа с удаляемой точкой;

- DopArray – дополнительный массив, необходимый при делении листа на новые узлы (тип TArrayOfPoints);

- midX, midY – координаты середины узла (тип real);

- PointsInNodes, numSZ, numSV, numYZ, numYV – переменные, использующиеся при подсчете числа точек в листах (тип real);

- there – индикатор наличия точки в дереве (тип boolean);

- N – число точек в листе (тип integer);

- i – счетчик цикла (тип integer).

· Словесный алгоритм

В начале своей работы функция проверяет, не является ли пустым параметр-указатель; если да – выход из подпрограммы. Если он не является листом, осуществляется цикл переходов к листу с нужными границами. Далее проверяется наличие точки в листе, и, если она там не обнаружена, процедура заканчивает свою работу; иначе происходит удаление точки из листа и последующая проверка общего числа точек в соседних листах. Если появилась возможность, соседние листы объединяются в один, старые удаляются.

2.1.4.3 ПроцедураClearTree

· Процедура предназначена для удаления всех элементов Q-дерева

· Параметры

- выходной параметр – указатель на узел дерева (тип PNode);

· Предусловия

Указатель на дерево не должен быть пустым

· Словесный алгоритм

В начале своей работы функция проверяет, не является ли пустым параметр-указатель; если да – выход из подпрограммы. Если он не является листом, осуществляются рекурсивные вызовы подпрограммы для каждого из его дочерних узлов; если параметр-указатель является листом, подпрограмма освобождает занятую им память и завершает свою работу.

2.1.4.4ФункцияFind

· Функция предназначена для поиска элементов Q-дерева, расположенных в заданной области карты

· Параметры

- входной параметр – указатель на узел дерева (тип PNode);

- параметр-константа – границы этого узла (тип TRect);

- параметр-константа – границы заданной области карты (тип TRect);

· Функция возвращает список (тип TList) элементов дерева, расположенных в заданной области

· Предусловия

Указатель на дерево не должен быть пустым

· Локальные переменные

- NewBounds – границы нового узла, передаваемые в качестве параметра в рекурсивном вызове функции (тип TRect);

- i – счетчик цикла (тип integer).

· Словесный алгоритм

В начале своей работы функция проверяет, не является ли пустым параметр-указатель; если да – выход из подпрограммы. Если часть площади узла находится в заданной области, осуществляются рекурсивные вызовы подпрограммы для каждого из его дочерних узлов. Для достигнутых таким образом листьев происходит проверка точек на принадлежность заданной области.

2.1.4.5ПроцедураSetProperties

· Процедура предназначена для выделения памяти и установки начальных характеристик для нового узла

· Параметры

- выходной параметр – указатель на узел дерева (тип PNode);

· Словесный алгоритм

Для нового узла, переданного в качестве параметра, выделяется память, устанавливаются начальные характеристики: тип узла (лист) и количество точек в нем (0).

· Подпрограмма используется функцией вставки точек в дерево при разделении листа на 4 новых.

2.1.4.6ПроцедураCopyPoints

· Процедура предназначена для копирования точек из листа в дополнительный массив

· Параметры

- входной параметр – указатель на узел дерева, из которого происходит копирование (тип PNode);

- выходной параметр – дополнительный массив, необходимый при делении листа на новые узлы (тип TArrayOfPoints);

- выходной параметр – счетчик элементов в дополнительном массиве (тип integer).

· Локальные переменные

- j – счетчик цикла (тип integer).

· Словесный алгоритм

Подпрограмма копирует значения точек из данного листа в дополнительный массив, одновременно увеличивая число его элементов, передаваемое в качестве параметра.

· Подпрограмма используется функцией удаления точек из дерева при объединении 4-х листов в один.

2.2 Модуль UnitMainForm

2.2.1 Назначение

В данном модуле описаны методы работы с Q-деревом точек

2.2.2 Функциональные требования, реализуемые модулем

· Подсчет количества элементов в дереве

· Отображение элементов дерева в виде точек на карте

· Возможность выбора области карты для просмотра содержащихся в ней точек

· Отображение точек заданной области карты в отдельном окне просмотра

· Отображение координат выбранных точек

2.2.3 Используемые компоненты

№	Имякомпонента	Класс	Настраиваемыесвойства		Значения	Обработанные события
1	MainForm	TMainForm	BorderStyle		bsSingle	OnCreate;OnKeyDown
			Caption		Q-дерево
			KeyPreview		True
2	MaxImage	TImage	–		–	OnCreate;OnMouseMove
3	MinImage	TImage	–		–	–
4	ShapeView	TShape	Brush	Style	bsClear	OnMouseDown;OnMouseMove;OnMouseUp
			Pen	Color	clRed

№	Имякомпонента	Класс	Настраиваемыесвойства	Значения	Обработанные события
5	SBtnCursor	TSpeedButton	Down	True	–
			GroupIndex	1
6	SBtnPoints	TSpeedButton	GroupIndex	1	–
7	ButtonDelete	TBitBtn	Caption	Удалить точку	OnClick
			Enabled	False
			ShowHint	True
			Hint	Удалить выбранную точку
8	ButtonClear	TBitBtn	Caption	Удалить все	OnClick
			ShowHint	True
			Hint	Удалить все точки дерева
9	StatusBar	TStatusBar	–	–	–

2.2.4 Глобальные переменные и константы модуля

Константы

· Xmax = 1024 – ширина всего квадрата, отведенного под Q-дерево;

- тип – целый;

- область видимости – внутри и вне модуля;

- используется в операциях вставки и удаления элементов для задания границ главного квадранта

· K = 10.56 – отношение длины стороны окна выделения к длине стороны окна просмотра;

- тип – вещественный;

- область видимости – внутри модуля;

- используется при выводе на карту изображений точек

· R = 3 – радиус точки, изображенной на карте;

- тип – целый;

- область видимости – внутри модуля;

- используется при выводе изображений точек

· LightColor = clYellow– цвет подсветки точек;

- тип – TColor;

- область видимости – внутри модуля;

- используется при выводе изображений точек

· SelectColor = clRed– цвет выделенной точки;

- тип – TColor;

- область видимости – внутри модуля;

- используется при выводе изображений точек

· BackColor = clBtnFace– цвет фона карты;

- тип – TColor;

- область видимости – внутри модуля;

- используется при выводе изображений точек.

Переменные

· Tree– указатель на корневой узел дерева;

- тип – PNode;

- область видимости – внутри модуля;

- используется в подпрограммах, работающих с деревом.

· X0, Y0 – начальные координаты указателя мыши при перемещении окна выделения;

- тип – целый;

- область видимости – внутри модуля;

- используются при определении координат просматриваемой области карты

· drag= false– индикатор перетаскивания окна выделения;

- тип – логический;

- область видимости – внутри модуля;

- используется при определении координат просматриваемой области карты

· PointCount = 0 – количество точек в дереве;

- тип – целый;

- область видимости – внутри модуля;

- используется для определения числа точек в дереве

· mainBounds, Query– координаты соответственно главного квадранта и выделенной области;

- тип – TRect;

- область видимости – внутри модуля;

- используются при поиске и выводе изображений точек просматриваемой области

· LightPoint, SelectedPoint– соответственно текущая и выделенная точки;

- тип – TPoint;

- область видимости – внутри модуля;

- используются для выбора и удаления точек.

2.2.5Подпрограммы модуля

2.2.5.1 Процедура DrawPoint

· Процедура предназначена для вывода изображений точек на карту

· Процедура является методом класса TMainForm

· Параметры

- параметр-константа – точка (тип TPoint);

- входной параметр – цвет изображенной точки (тип TColor);

· Локальные переменные

- dopX, dopY – координаты точки относительно окна просмотра (тип integer).

· Словесный алгоритм

Процедура вычисляет координаты отображаемой точки для каждой из карт (большой и малой) и рисует точку в виде эллипса радиусом R.

2.2.5.2 Процедура ClearBackground

· Процедура стирает предыдущее изображение на карте

· Процедура является методом класса TMainForm

· Параметры

- входной параметр – компонент-карта (тип TImage);

· Словесный алгоритм

Процедура закрашивает поверхность карты цветом фона BackColor.

2.2.5.3 Процедура DrawRegion

· Процедура предназначена для поиска и вывода изображений точек дерева в заданной области карты

· Процедура является методом класса TMainForm

· Параметры

- параметр-константа – указатель на узел дерева (тип PNode);

- параметр-константа – границы заданной области (тип TRect);

· Локальные переменные

- FindedPoints – список найденных точек (тип TList);

- dopPoint – точка из списка (тип TPoint);

- i –счетчик цикла (тип integer).

· Словесный алгоритм

Процедура создает пустой список, копирует туда точки дерева, найденные в заданной области, и выводит их изображения на карты.

2.2.5.4Процедура FormCreate

· Процедура предназначена для задания начальных координат областей и точек