Учебная работа. Курсовая работа: Структура данных программного комплекса Q-дерево

Учебная работа. Курсовая работа: Структура данных программного комплекса Q-дерево

Реферат

Представляемый документ содержит:

52 странички текста и перечень из 2-ух источников.

Объектом исследования является структура данных «Q-дерево».

Цель работы состоит в разработке программного комплекса, обеспечивающего работу со структурой данных «Q-дерево», представленной в виде модели. способы, применяемые при разработке, – язык программирования высочайшего уровня ObjectPascal. Сделанный программный продукт обеспечивает выполнение всех требований технического задания.

Содержание

Введение

1. Техническое задание

1.1 Основание для разработки

1.2 Предназначение разработки

1.3Функциональные требования к программке

1.4 Требования к составу и характеристикам технических средств

1.5 Требования к информационной и программной сопоставимости

1.6 Требования к программной документации

1.7 порядок контроля и приемки

2. Рабочий проект

2.1 Модуль UnitModel

2.1.1 Предназначение

2.1.2 Многофункциональные требования, реализуемые модулем

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

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

2.2 Модуль UnitMainForm

2.2.1 Предназначение

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

2.2.3 Применяемые составляющие

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

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

Заключение

Перечень применяемых источников

приложение

Введение

Цель данной курсовой работы – разработка программного продукта, созданного для работы со структурой данных «Q-дерево». Существует огромное количество разных структур данных, созданных для работы с огромными количествами: деревья, массивы и так дальше. Посреди их есть Q-деревья, дозволяющие хранить огромного количества точек и обеспечивать к ним резвый и удачный доступ. Практическое работы с огромными количествами. Программный продукт должен быть разработан на языке программирования высочайшего уровня ObjectPascal, применять принципы объектно-ориентированного программирования и структурный подход к решению намеченных целей.

Результатом выполнения курсовой работы должен стать готовый программный продукт, отвечающий всем требованиям технического задания.

1.
Техническое задание





1.1
Основание для разработки

Основанием для разработки программного продукта служит задание на курсовую работу “Q-дерево точек”.

1.2 Предназначение разработки

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

1.3 Многофункциональные требования к программке

1. Возможность прибавления частей в дерево

2. Удаление частей из дерева

3. Чистка дерева

4. Подсчет количества частей

5. Отображение частей дерева в виде точек на карте

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

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

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

9. Отображение координат избранных точек

1.4
Требования к составу и характеристикам технических средств

Программный комплекс должен корректно работать на компе со последующими техническими чертами:

− процессорIntel® Celeron® CPU 2.40 ГГц;

− оперативная память объемом 512 Мб;

− твердый диск Seagate ST380011A, объемом 80 Гб;

−

− клавиатура;

− манипулятор типа “мышь”.

1.5 Требования к информационной и программной сопоставимости

Для работы программки нужна операционная система MicrosoftWindowsXPProfessional 2002 (SP1-2).

1.6 Требования к программной документации

Программная документация обязана включать последующие документы:

· техническое задание;

· рабочий проект.

В приложении к документу «Рабочий проект» должен быть приведен листинг начальных текстов программного изделия.

1.7 порядок контроля и приемки


1.7.1 Возможность прибавления частей в дерево,
подсчет количества частей

Добавление частей в дерево делается щелчком левой клавишей мыши по точке с подходящими координатами в окне просмотра (рис. 1)

Рис. 1

Итог: добавление точки в дерево и его перерисовка; повышение количества точек в дереве на единицу.

1.7.2 Удаление частей из дерева, подсчет количества частей

Удаление элемента делается методом выделения точки при помощи мыши в окне просмотра в режиме выделения точек и щелчка по кнопочке «Удалить точку» (рис. 2)

Рис. 2

Итог: удаление точки из дерева и его перерисовка; уменьшение количества точек в дереве на единицу.

1.7.3 Чистка дерева

Чистка дерева (удаление всех частей) делается щелчком по кнопочке «Удалить все» (рис. 3)

Рис. 3

Итог: удаление всех частей дерева и соответственная перерисовка изображений

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

Выбор области просмотра осуществляется перемещением окна выделения при помощи мыши либо кнопок (рис. 4)

Рис. 4

Итог: перемещение окна выделения, поиск и отрисовка точек, находящихся в выделенной области карты.

1.7.5 Отображение частей дерева в виде точек на карте, отображение координат избираемых точек

Выбор точки делается при помощи щелчка левой клавишей мыши по точке с подходящими координатами в режиме выбора точек (рис. 5)

Рис. 5

Итог: отображение координат избранной точки в строке состояния; перерисовка подходящим цветом ее изображения в окне просмотра.

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

Для получения координат точки без ее выделения довольно навести указатель мыши на ее изображение в окне просмотра (рис. 6)

Рис. 6

Итог: отображение координат точки в строке состояния без ее выбора; перерисовка подходящим цветом ее изображения в окне просмотра.

2.
Рабочий проект






2.1
Модуль UnitModel
2.1.1 Предназначение

Данный модуль представляет собой реализацию модели структуры данных «Q-дерево точек».

2.1.2 Многофункциональные требования, реализуемые модулем

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

· Удаление частей из дерева

· Чистка дерева

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

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

Константы

· М = 3 – наибольшее число точек в листе;

— тип – целый;

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

— употребляется в операциях вставки и удаления частей дерева для проверки числа точек в листьях.

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


2.1.4.1 Функция

InsertPoint

· Функция создана для вставки новейшего элемента в Q-дерево

· характеристики

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

— входной параметр – границы этого узла (тип TRect);

— входной параметр – координаты вставляемой точки (тип TPoint);

· Функция возвращает логическое

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

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

— DopArray– доп массив, нужный при делении листа на новейшие узлы (тип TArrayOfPoints);

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

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

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

· Словесный метод

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

2.1.4.
2
Процедура
DeletePoint

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

· характеристики

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

— входной параметр – границы этого узла (тип TRect);

— входной параметр – координаты вставляемой точки (тип TPoint);

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

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

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

— 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

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

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

· характеристики

— входной параметр – объект, сгенерировавший событие (тип TObject)

· Словесный метод

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

2.

2
.
5
.
5
Процедура
ShapeViewMouseDown

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

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

· характеристики

— входной параметр – объект, сгенерировавший событие (тип TObject);

— входной параметр – индикатор нажатой клавиши мыши (тип TMouseButton);

— входной параметр – индикатор нажатой клавиши (тип TShiftState);

— входные характеристики – координаты указателя мыши (тип integer)

· Словесный метод

Координаты указателя записываются в глобальные переменные X0 и Y0. Индикатору перетаскивания drag присваивается true.

2.1.5.6 Процедура

ShapeViewMouseUp

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

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

· характеристики

— входной параметр – объект, сгенерировавший событие (тип TObject);

— входной параметр – индикатор нажатой клавиши мыши (тип TMouseButton);

— входной параметр – индикатор нажатой клавиши (тип TShiftState);

— входные характеристики – координаты указателя мыши (тип integer)

· Словесный метод

Индикатору перетаскивания drag присваивается false.

2.1.

5
.7
Процедура
ShapeViewMouseMove

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

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

· характеристики

— входной параметр – объект, сгенерировавший событие (тип TObject);

— входной параметр – индикатор нажатой клавиши (тип TShiftState)

— входные характеристики – координаты указателя мыши (тип integer)

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

Индикатор перетаскивания должен быть равен true.

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

— newLeft, newTop – новейшие координаты окна выделения (тип integer)

· Словесный метод

Процедура вычисляет новейшие координаты окна выделения и области просмотра с внедрением глобальных переменных X0 и Y0; потом производит поиск и вывод на карту изображений точек из новейшей области при помощи процедуры DrawRegion.

2.1.

5
.
8
Процедура
MaxImageMouseMove

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

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

· характеристики

— входной параметр – объект, сгенерировавший событие (тип TObject);

— входной параметр – индикатор нажатой клавиши (тип TShiftState);

— входные характеристики – координаты указателя мыши (тип integer)

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

—

— Rect – область поиска точки в дереве (тип TRect);

— str – строчка с координатами избранной точки (тип string);

— List – перечень точек, отысканных в области поблизости указателя мыши

· Словесный метод

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

2.1.5.9 Процедура

MaxImageClick

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

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

· характеристики

— входной параметр – объект, сгенерировавший событие (тип TObject)

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

—

— str – строчка с координатами избранной точки (тип string);

— i, j – координаты точки относительно окна просмотра (тип integer)

· Словесный метод

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

2.1.

5
.
10
Процедура
ButtonDeleteClick

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

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

· характеристики

— входной параметр – объект, сгенерировавший событие (тип TObject)

· Словесный метод

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

2.1.
5.11ПроцедураButtonClearClick

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

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

· характеристики

— входной параметр – объект, сгенерировавший событие (тип TObject)

· Словесный метод

Подпрограмма удаляет все точки из дерева, «стирает» изображение с карты и устанавливает «пустые » координаты для избранной и текущей точек.

2.1.

5
.
12
Процедура
FormKeyDown

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

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

· характеристики

— входной параметр – объект, сгенерировавший событие (тип TObject);

— выходной параметр – индикатор нажатой клавиши (тип Word);

— входной параметр – индикатор нажатой клавиши (тип TShiftState)

· Локальные константы

– dif = 4 – число пикселей, на которое {перемещается} окно выделения

· Словесный метод

Подпрограмма вызывает перемещающую окно выделения функцию ShapeViewMouseMove, передавая ей различные характеристики зависимо от нажатой клавиши.

Заключение

Разработанный программный продукт обеспечивает выполнение всех требований, предъявленных к нему в техническом задании.

Программный продукт рекомендован к использованию для широкого круга юзеров. Внедрение программного продукта дозволяет значительно облегчить работу с огромными количествами и убыстрить их обработку.

Перечень применяемых источников

1 Сухарев М.В. Базы Delphi. Проф подход – СПб.: Наука и техника, 2004.

2 Кэнту М. Delphi 7: для экспертов – СПб.: Питер, 2004.

приложение

Текст программки

program Qtree;

usesForms,

UnitMainForm in ‘UnitMainForm.pas’ {MainForm},

UnitModel in ‘UnitModel.pas’;

{$R *.res}

begin

Application.Initialize;

Application.CreateForm(TMainForm, MainForm);

Application.Run;

end.

unit UnitModel;

interface

uses Classes;

constM = 3; //число точек в листе

type

//Тип узла дерева————————————

TNodeKind = (nkBranch, nkLeaf);

TPoint = record

X: real;

Y: real;

end;

TRect = record

X1, Y1, X2, Y2: real;

end;

//Массив для хранения точек в листе——————

TArrayOfPoints = array[1..M] of TPoint;

//Узел дерева—————————————

PNode = ^TNode;

TNode = packed record

case Kind: TNodeKind of

nkBranch: (SZ, SV, YZ, YV: PNode);

nkLeaf: (Points: TArrayOfPoints;

PointsCount: integer);

end;

function InsertPoint(var Node: PNode; Bounds: TRect;

procedure DeletePoint(var Node: PNode; Bounds: TRect;

procedure ClearTree(var Node: PNode);

function Find(Node: PNode; const Bounds, Rect: TRect): TList;

implementation

//установка черт новейшего листа =======================================

procedure SetProperties(var ChildNode: PNode);

begin

New(ChildNode);

ChildNode^.Kind:= nkLeaf;

ChildNode^.PointsCount:= 0; //в массиве нет точек

end;

//Копирование точек из листа в доп массив =========================

procedure CopyPoints(Node: PNode; var DopArray: TArrayOfPoints; var i: integer);

var j: integer;

begin

for j:=1 to Node^.PointsCount do

begin

DopArray[i]:= Node^.Points[j];

inc(i);

end;

end;

//ВСТАВКА ТОЧКИ В ДЕРЕВО =====================================================

function InsertPoint(var Node: PNode; Bounds: TRect;

var CurNode: PNode; //текущий квадрант

DopArray: TArrayOfPoints; //дополнительныймассив (когдаделимузел)

i: integer;

midX, midY: real;

NewBounds: TRect;

begin

if Node = nil then

begin

New(Node);

Node^.Kind:= nkLeaf;

Node^.PointsCount:= 0;

end;

CurNode:= Node;

Result:= true;

with Bounds do

begin

while CurNode^.Kind = nkBranch do //если ветвь, то смотрим, куда идти

begin

midX:= (X2 — X1)/2 + X1;

midY:= (Y2 — Y1)/2 + Y1;

if

if

begin

CurNode:= CurNode^.SZ;

X2:= midX;

Y2:= midY;

end

else

begin

CurNode:= CurNode^.YZ;

Y1:= midY;

X2:= midX;

end

else

if

begin

CurNode:= CurNode^.SV;

X1:= midX;

Y2:= midY;

end

else

begin

CurNode:= CurNode^.YV;

X1:= midX;

Y1:= midY;

end;

end;

midX:= (X2 — X1)/2 + X1;

midY:= (Y2 — Y1)/2 + Y1;

end;

//Фактически вставка———————————————————-

//Проверить, есть ли пространство в массиве точек и нет ли уже там новейшей:

for i:=1 to CurNode^.PointsCount do

if (CurNode^.Points[i].X =

begin

Result:= false;

Exit;

end;

//Если массив не заполнен, вставляем точку…

if CurNode^.PointsCount < M then

begin

CurNode^.Points[CurNode^.PointsCount + 1]:=

CurNode^.PointsCount:= CurNode^.PointsCount + 1;

end

else

begin

//…по другому делим лист на 4 новейших:

DopArray:= CurNode^.Points;

CurNode^.Kind:= nkBranch;

SetProperties(CurNode^.SZ);

SetProperties(CurNode^.SV);

SetProperties(CurNode^.YZ);

SetProperties(CurNode^.YV);

//Распределение точек по узлам

fori:=1 toMdo

with Bounds do

if DopArray[i].X < midX then

if DopArray[i].Y < midY then

begin

NewBounds.X1:= X1;

NewBounds.X2:= (X2 — X1)/2 + X1;

NewBounds.Y1:= Y1;

NewBounds.Y2:= (Y2 — Y1)/2 + Y1;

InsertPoint(CurNode^.SZ, NewBounds, DopArray[i]);

end

else

begin

NewBounds.X1:= X1;

NewBounds.X2:= (X2 — X1)/2 + X1;

NewBounds.Y1:= (Y2 — Y1)/2 + Y1;

NewBounds.Y2:= Y2;

InsertPoint(CurNode^.YZ, NewBounds, DopArray[i]);

end

else

if DopArray[i].Y < midY then

begin

NewBounds.X1:= (X2 — X1)/2 + X1;

NewBounds.X2:= X2;

NewBounds.Y1:= Y1;

NewBounds.Y2:= (Y2 — Y1)/2 + Y1;

InsertPoint(CurNode^.SV, NewBounds, DopArray[i]);

end

else

begin

NewBounds.X1:= (X2 — X1)/2 + X1;

NewBounds.X2:= X2;

NewBounds.Y1:= (Y2 — Y1)/2 + Y1;

NewBounds.Y2:= Y2;

InsertPoint(CurNode^.YV, NewBounds, DopArray[i]);

end;

//Вставка новейшей точки

InsertPoint(CurNode, Bounds,

end;

end;

//УДАЛЕНИЕ ТОЧКИ ИЗ ДЕРЕВА ===================================================

procedure DeletePoint(var Node: PNode; Bounds: TRect;

var CurNode, ParentNode: PNode;

DopArray: TArrayOfPoints;

midX, midY, PointsInNodes, numSZ, numSV, numYZ, numYV: real;

there: boolean;

i, N: integer;

begin

if Node = nil then

Exit;

CurNode:= Node;

ParentNode:= CurNode;

with Bounds do

while CurNode^.Kind = nkBranch do //если ветвь, то смотрим, куда идти

begin

ParentNode:= CurNode;

midX:= (X2 — X1)/2 + X1;

midY:= (Y2 — Y1)/2 + Y1;

if

if

begin

CurNode:= CurNode^.SZ;

X2:= midX;

Y2:= midY;

end

else

begin

CurNode:= CurNode^.YZ;

Y1:= midY;

X2:= midX;

end

else

if

begin

CurNode:= CurNode^.SV;

X1:= midX;

Y2:= midY;

end

else

begin

CurNode:= CurNode^.YV;

X1:= midX;

Y1:= midY;

end;

end;

//Фактически удаление——————————————————-

N:= CurNode^.PointsCount;

//Проверить, есть ли в массиве удаляемая точка:

there:= false;

for i:=1 to M do

if (CurNode^.Points[i].X =

begin

there:= true;

break;

end;

//Удаляем точку (или выходим, если такой не имеется)

if there then

begin

CurNode^.Points[i]:= CurNode^.Points[N];

CurNode^.PointsCount:= CurNode^.PointsCount — 1;

end

else Exit;

if Node^.Kind = nkLeaf then

Exit;

//Поглядим, можно ли соединить примыкающие узлы

numSZ:= ParentNode^.SZ^.PointsCount;

numSV:= ParentNode^.SV^.PointsCount;

numYZ:= ParentNode^.YZ^.PointsCount;

numYV:= ParentNode^.YV^.PointsCount;

PointsInNodes:= numSZ + numSV + numYZ + numYV;

ifPointsInNodes <= Mthen

begin

//Точки из всех листьев переносим в вышестоящий узел

i:=1;

CopyPoints(ParentNode^.SZ, DopArray, i);

CopyPoints(ParentNode^.SV, DopArray, i);

CopyPoints(ParentNode^.YZ, DopArray, i);

CopyPoints(ParentNode^.YV, DopArray, i);

//Удаляем старенькые листья

Dispose(ParentNode^.SZ);

Dispose(ParentNode^.SV);

Dispose(ParentNode^.YZ);

Dispose(ParentNode^.YV);

ParentNode^.Kind:= nkLeaf;

ParentNode^.Points:= DopArray;

end;

end;

//УДАЛЕНИЕ ДЕРЕВА ============================================================

procedure ClearTree(var Node: PNode);

begin

if Node = nil then

Exit;

if Node^.Kind = nkBranch then

begin

ClearTree(Node^.SZ);

ClearTree(Node^.SV);

ClearTree(Node^.YZ);

ClearTree(Node^.YV);

end;

Dispose(Node);

Node:= nil;

end;

//ПОИСК ТОЧЕК В ЗАДАННОЙ области =============================================

function Find(Node: PNode; const Bounds, Rect: TRect): TList;

var NewBounds: TRect;

i: integer;

begin

Result:= TList.Create;

if Node = nil then

Exit;

with Bounds do

if (X2 >= Rect.X1)and(X1 <= Rect.X2)and(Y2 >= Rect.Y1)and(Y1 <= Rect.Y2) then

if Node^.Kind = nkBranch then

begin

NewBounds.X1:= X1;

NewBounds.X2:= (X2 — X1)/2 + X1;

NewBounds.Y1:= Y1;

NewBounds.Y2:= (Y2 — Y1)/2 + Y1;

Result.Assign(Find(Node^.SZ, NewBounds, Rect), laOr);

NewBounds.X1:= (X2 — X1)/2 + X1;

NewBounds.X2:= X2;

NewBounds.Y1:= Y1;

NewBounds.Y2:= (Y2 — Y1)/2 + Y1;

Result.Assign(Find(Node^.SV, NewBounds, Rect), laOr);

NewBounds.X1:= X1;

NewBounds.X2:= (X2 — X1)/2 + X1;

NewBounds.Y1:= (Y2 — Y1)/2 + Y1;

NewBounds.Y2:= Y2;

Result.Assign(Find(Node^.YZ, NewBounds, Rect), laOr);

NewBounds.X1:= (X2 — X1)/2 + X1;

NewBounds.X2:= X2;

NewBounds.Y1:= (Y2 — Y1)/2 + Y1;

NewBounds.Y2:= Y2;

Result.Assign(Find(Node^.YV, NewBounds, Rect), laOr);

end

else

begin

for i:=1 to Node^.PointsCount do

if (Node^.Points[i].X >= Rect.X1)and

(Node^.Points[i].X <=Rect.X2)and

(Node^.Points[i].Y >= Rect.Y1)and

(Node^.Points[i].Y <= Rect.Y2) then

Result.Add(@(Node^.Points[i]));

end;

end;

end.

unit UnitMainForm;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, ExtCtrls, StdCtrls, UnitModel, ComCtrls, Buttons;

constXmax = 1024; //ширина всего квадрата, отведенного под квадродерево

type

TMainForm = class(TForm)

MaxImage: TImage;

ShapeMax: TShape;

MinImage: TImage;

ShapeView: TShape;

Shape3: TShape;

LabelTop: TLabel;

LabelLeft: TLabel;

LabelRight: TLabel;

LabelBottom: TLabel;

StatusBar: TStatusBar;

SBtnCursor: TSpeedButton;

SBtnPoints: TSpeedButton;

ButtonClear: TBitBtn;

ButtonDelete: TBitBtn;

procedure DrawPoint(const

procedure ClearBackground(Image: TImage);

procedure DrawRegion(const Node: PNode; const Bounds: TRect);

procedure ShapeViewMouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure ShapeViewMouseUp(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure ShapeViewMouseMove(Sender: TObject; Shift: TShiftState; X,

Y: Integer);

procedure MaxImageMouseMove(Sender: TObject; Shift: TShiftState; X,

Y: Integer);

procedure MaxImageClick(Sender: TObject);

procedure FormCreate(Sender: TObject);

procedure ButtonClearClick(Sender: TObject);

procedure ButtonDeleteClick(Sender: TObject);

procedure FormKeyDown(Sender: TObject; var Key: Word; Shift: TShiftState);

private

{ Private declarations }

public

{ Public declarations }

end;

var

MainForm: TMainForm;

implementation

{$R *.dfm}

const K = 10.56; //масштаб (MaxImage.Width/MinImage.Width)

R = 3; //радиус точки на форме

LightColor = clLime; //цвет подсветки точек

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

BackColor = clWhite; //цвет фона

var Tree: PNode;

X0, Y0: integer;

drag: boolean = false; //флаг перетаскивания окна просмотра

PointCount: integer = 0; //число точек в дереве

mainBounds, Query: TRect; //основной квадрант и окно просмотра

LightPoint, SelectedPoint: TPoint;

//Отрисовка точки ============================================================

procedure TMainForm.DrawPoint(const

var dopX, dopY: integer;

begin

//В большенном окне…

with

begin

with MaxImage.Canvas do

begin

Brush.Color:= PointColor;

Brush.Style:= bsSolid;

Pen.Color:= PointColor;

dopX:= round(X — Query.X1);

dopY:= round(Y — Query.Y1);

Ellipse(dopX-R, dopY-R, dopX+R, dopY+R);

end;

//…и в малом:

with MinImage.Canvas do

begin

Brush.Color:= PointColor;

Brush.Style:= bsSolid;

Pen.Color:= PointColor;

Ellipse(round(X/K)-1, round(Y/K)-1, round(X/K)+1, round(Y/K)+1);

end;

end;

end;

//»Чистка» фона=============================================================

procedure TMainForm.ClearBackground(Image: TImage);

begin

with Image.Canvas do

begin

Brush.Style:= bsSolid;

Brush.Color:= BackColor;

Rectangle(-1,-1,Image.Width + 1,Image.Height + 1);

end;

end;

//Отрисовка просматриваемой области ==========================================

procedure TMainForm.DrawRegion(const Node: PNode; const Bounds: TRect);

var FindedPoints: TList;

dopPoint: TPoint;

i: integer;

begin

FindedPoints:= TList.Create;

with FindedPoints do

begin

Assign(Find(Node, mainBounds, Bounds), laOr);

if Capacity <> 0 then

for i:= 0 to Count — 1 do

begin

dopPoint:= TPoint(FindedPoints[i]^);

if (dopPoint.X = SelectedPoint.X)and(dopPoint.Y = SelectedPoint.Y) then

DrawPoint(dopPoint, SelectColor)

else DrawPoint(dopPoint, clBlack);

end;

Free;

end;

end;

//Задание исходных координат областей и точек ===============================

procedure TMainForm.FormCreate(Sender: TObject);

begin

with mainBounds do

begin

X1:= 0;

Y1:= 0;

X2:= Xmax;

Y2:= Xmax;

end;

with Query do

begin

X1:= 0;

Y1:= 0;

X2:= MaxImage.Width;

Y2:= MaxImage.Width;

end;

with LightPoint do

begin

X:= -4;

Y:= -4;

end;

with SelectedPoint do

begin

X:= -3;

Y:= -3;

end;

end;

//НАВИГАЦИЯ В МАЛОМ ОКНЕ =====================================================

procedure TMainForm.ShapeViewMouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

begin

X0:= X;

Y0:= Y;

drag:= true;

end;

procedure TMainForm.ShapeViewMouseUp(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

begin

drag:= false;

end;

procedure TMainForm.ShapeViewMouseMove(Sender: TObject; Shift: TShiftState;

X, Y: Integer);

var newLeft, newTop: integer;

begin

if drag then

with Sender as TShape do

begin

newLeft:= Left + X — X0;

newTop:= Top + Y — Y0;

if newLeft + Width >= MinImage.Left + MinImage.Width + 1 then

newLeft:= MinImage.Left + MinImage.Width + 1 — Width;

if newLeft <= MinImage.Left — 1 then

newLeft:= MinImage.Left — 1;

Left:= newLeft;

if newTop + Height >= MinImage.Top + MinImage.Height + 1 then

newTop:= MinImage.Top + MinImage.Height + 1 — Height;

if newTop <= MinImage.Top — 1 then

newTop:= MinImage.Top — 1;

Top:= newTop;

//Границы просматриваемой области————————————

Query.X1:= round((Left — MinImage.Left + 1)*K);

Query.X2:= round((Left — MinImage.Left + Width + 1)*K);

Query.Y1:= round((Top — MinImage.Top + 1)*K);

Query.Y2:= round((Top — MinImage.Top + Height + 1)*K);

LabelLeft.Caption:= FloatToStr(Query.X1);

LabelRight.Caption:= FloatToStr(Query.X2);

LabelTop.Caption:= FloatToStr(Query.Y1);

LabelBottom.Caption:= FloatToStr(Query.Y2);

ClearBackground(MaxImage);

DrawRegion(Tree, Query);

end;

end;

//Отображение координат точек в строке состояния =============================

procedure TMainForm.MaxImageMouseMove(Sender: TObject; Shift: TShiftState;

X, Y: Integer);

var

Rect: TRect;

str: string[30];

List: TList;

begin

if SBtnCursor.Down then

MaxImage.Cursor:= crDefault

else MaxImage.Cursor:= crCross;

with StatusBar do

with MaxImage.Canvas do

begin

//Координаты указателя мыши

Panels[0].Text := ‘X: ‘ + FloatToStr(X + Query.X1);

Panels[1].Text := ‘Y: ‘ + FloatToStr(Y + Query.Y1);

//Если указатель наведен на точку:

if (Pixels[X,Y] = clBlack)or(Pixels[X,Y] = LightColor)or

(Pixels[X,Y] = SelectColor) then

begin

with Point do

begin

Rect.X1:= X — R;

Rect.X2:= X + R;

Rect.Y1:= Y — R;

Rect.Y2:= Y + R;

end;

List:= TList.Create;

List.Assign(Find(Tree, mainBounds, Rect), laOr);

if List.Capacity <> 0 then

begin

Panels[3].Text:= ‘Точка ‘ + FloatToStr(

FloatToStr(

//»Подсветка» точки———————————————-

if Pixels[round(

LightColor then

with LightPoint do

begin

if X >= 0 then

if (X <> SelectedPoint.X)or(Y <> SelectedPoint.Y) then

DrawPoint(LightPoint, clBlack)

else DrawPoint(LightPoint, SelectColor);

str:= StatusBar.Panels[3].Text;

X:= StrToFloat(Copy(str, Pos(‘ ‘, str)+1, Pos(‘;’, str)-

Pos(‘ ‘, str)-1));

Y:= StrToFloat(Copy(str, Pos(‘;’, str)+2, 10));

DrawPoint(LightPoint, LightColor);

end;

List.Free;

end;

end

else

//Долой «подсветку»:

with LightPoint do

begin

Panels[3].Text:= »;

if Tree = nil then

Exit;

if Pixels[round(X — Query.X1), round(Y — Query.Y1)] =

LightColor then

if (X = SelectedPoint.X)and(Y = SelectedPoint.Y) then

DrawPoint(LightPoint, SelectColor)

else DrawPoint(LightPoint, clBlack);

end;

end;

end;

//Клик по большенному окну ======================================================

procedure TMainForm.MaxImageClick(Sender: TObject);

var

str: string[30];

i, j: integer;

begin

ifSBtnPoints.Downthen //В режиме прибавления точек ————————

begin

//Добавление точки в дерево

if InsertPoint(Tree, mainBounds,

PointCount:= PointCount + 1;

ClearBackground(MaxImage);

ClearBackground(MinImage);

//Перерисовка области просмотра

DrawRegion(Tree, Query);

DrawRegion(Tree, mainBounds);

StatusBar.Panels[2].Text:= ‘количество точек: ‘ + IntToStr(PointCount);

end

else

begin

if (

Exit;

i:= round(

j:= round(

with MaxImage.Canvas do

begin

if (Pixels[i,j] = LightColor)or(Pixels[i,j] = clBlack) then

//»Уяснить» избранную точку ————————————-

withSelectedPointdo

begin

str:= StatusBar.Panels[3].Text;

if str = » then

Exit;

if X >= 0 then

DrawPoint(SelectedPoint, clBlack);

X:= StrToFloat(Copy(str, Pos(‘ ‘, str)+1, Pos(‘;’, str)-Pos(‘ ‘,

str)-1));

Y:= StrToFloat(Copy(str, Pos(‘;’, str)+2, 10));

StatusBar.Panels[4].Text:= ‘Выбрано: ‘ + FloatToStr(X) + ‘; ‘ +

FloatToStr(Y);

DrawPoint(SelectedPoint, SelectColor);

ButtonDelete.Enabled:= true;

end;

end;

end;

end;

//Удаление точки =============================================================

procedure TMainForm.ButtonDeleteClick(Sender: TObject);

begin

DeletePoint(Tree, mainBounds, SelectedPoint);

if (SelectedPoint.X >= Query.X1)and(SelectedPoint.X <= Query.X2)and

(SelectedPoint.Y >= Query.Y1)and(SelectedPoint.Y <= Query.Y2) then

begin

SelectedPoint.X:= -3;

LightPoint.X:= -4;

ClearBackground(MaxImage);

ClearBackground(MinImage);

DrawRegion(Tree, mainBounds);

end;

PointCount:= PointCount — 1;

StatusBar.Panels[4].Text:= »;

ButtonDelete.Enabled:= false;

end;

//Удаление дерева ============================================================

procedure TMainForm.ButtonClearClick(Sender: TObject);

begin

ClearTree(Tree);

ClearBackground(MaxImage);

ClearBackground(MinImage);

DrawRegion(Tree, mainBounds);

PointCount:= 0;

with StatusBar do

begin

Panels[2].Text:= »;

Panels[3].Text:= »;

Panels[4].Text:= »;

end;

SelectedPoint.X:= -3;

LightPoint.X:= -4;

StatusBar.Panels[4].Text:= »;

ButtonDelete.Enabled:= false;

end;

//Перемещение окошка при помощи кнопок ========================================

procedure TMainForm.FormKeyDown(Sender: TObject; var Key: Word;

Shift: TShiftState);

const dif = 4;

begin

drag:= true;

with ShapeView do

begin

X0:= Left + round(Width/2);

Y0:= Top + round(Height/2);

end;

if Key = VK_UP then

ShapeViewMouseMove(ShapeView, Shift, X0, Y0 — dif)

else

if Key = VK_DOWN then

ShapeViewMouseMove(ShapeView, Shift, X0, Y0 + dif)

else

if Key = VK_LEFT then

ShapeViewMouseMove(ShapeView, Shift, X0 — dif, Y0)

else

ShapeViewMouseMove(ShapeView, Shift, X0 + dif, Y0);

drag:= false;

end;

end.

]]>