Главная Учебники - Разные Лекции (разные) - часть 34
|
Представляемый документ содержит: 52 страницы текста и список из двух источников. Объектом исследования является структура данных «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-деревья, позволяющие хранить множества точек и обеспечивать к ним быстрый и удобный доступ. Практическое значение. Программный продукт позволяет пользоваться Q-деревьями. Актуальность разработки программного продукта состоит в увеличении скорости работы с множествами. Программный продукт должен быть разработан на языке программирования высокого уровня ObjectPascal, использовать принципы объектно-ориентированного программирования и структурный подход к решению поставленных задач. Результатом выполнения курсовой работы должен стать готовый программный продукт, отвечающий всем требованиям технического задания. Основанием для разработки программного продукта служит задание на курсовую работу “Q-дерево точек”. Программный продукт разрабатывается для работы с Q-деревьями точек. 1. Возможность добавления элементов в дерево 2. Удаление элементов из дерева 3. Очистка дерева 4. Подсчет количества элементов 5. Отображение элементов дерева в виде точек на карте 6. Поиск точек в заданной прямоугольной области карты 7. Возможность выбора области карты для просмотра содержащихся в ней точек 8. Отображение точек заданной области карты в отдельном окне просмотра 9. Отображение координат выбранных точек Программный комплекс должен корректно работать на компьютере со следующими техническими характеристиками: − процессорIntel® Celeron® CPU 2.40 ГГц; − оперативная память объемом 512 Мб; − жесткий диск Seagate ST380011A, объемом 80 Гб; − видеоадаптер AGP 8X; − клавиатура; − манипулятор типа “мышь”. Для работы программы необходима операционная система MicrosoftWindowsXPProfessional 2002 (SP1-2). Программная документация должна включать следующие документы: · техническое задание; · рабочий проект. В приложении к документу "Рабочий проект" должен быть приведен листинг исходных текстов программного изделия. Добавление элементов в дерево производится щелчком левой кнопкой мыши по точке с нужными координатами в окне просмотра (рис. 1) Рис. 1 Результат: добавление точки в дерево и его перерисовка; увеличение количества точек в дереве на единицу. Удаление элемента производится путем выделения точки с помощью мыши в окне просмотра в режиме выделения точек и щелчка по кнопке «Удалить точку» (рис. 2) Рис. 2 Результат: удаление точки из дерева и его перерисовка; уменьшение количества точек в дереве на единицу. Очистка дерева (удаление всех элементов) производится щелчком по кнопке «Удалить все» (рис. 3) Рис. 3 Результат: удаление всех элементов дерева и соответствующая перерисовка изображений Выбор области просмотра осуществляется перемещением окна выделения с помощью мыши или клавиш (рис. 4) Рис. 4 Результат: перемещение окна выделения, поиск и отрисовка точек, находящихся в выделенной области карты. Выбор точки производится с помощью щелчка левой кнопкой мыши по точке с нужными координатами в режиме выбора точек (рис. 5) Рис. 5 Результат: отображение координат выбранной точки в строке состояния; перерисовка соответствующим цветом ее изображения в окне просмотра. Для получения координат точки без ее выделения достаточно навести указатель мыши на ее изображение в окне просмотра (рис. 6) Рис. 6 Результат: отображение координат точки в строке состояния без ее выбора; перерисовка соответствующим цветом ее изображения в окне просмотра. Данный модуль представляет собой реализацию модели структуры данных «Q-дерево точек». · Возможность добавления элементов в дерево · Удаление элементов из дерева · Очистка дерева · Поиск точек в заданной прямоугольной области карты. Константы · М = 3 – максимальное число точек в листе; - тип – целый; - область видимости – внутри и вне модуля; - используется в операциях вставки и удаления элементов дерева для проверки числа точек в листьях. · Функция предназначена для вставки нового элемента в Q-дерево · Параметры - выходной параметр – указатель на узел дерева, в которое вставляется элемент (тип PNode); - входной параметр – границы этого узла (тип TRect); - входной параметр – координаты вставляемой точки (тип TPoint); · Функция возвращает логическое значение (тип boolean), указывающее на изменение количества элементов в дереве · Локальные переменные - CurNode – текущий квадрант (тип PNode); - DopArray– дополнительный массив, необходимый при делении листа на новые узлы (тип TArrayOfPoints); - midX, midY– координаты середины узла (тип real); - NewBounds– границы нового узла, передаваемые в качестве параметра в рекурсивном вызове функции (тип TRect); - i – счетчик цикла (тип integer). · Словесный алгоритм В начале своей работы функция проверяет, не является ли пустым параметр-указатель; если да, то для него выделяется память, устанавливаются начальные значения полей и вставляется новый элемент. Если он не является листом, осуществляется цикл переходов к листу с нужными границами. Далее проверяется число элементов в листе, и, если оно меньше допустимого, туда вставляется новая точка; иначе этот лист разделяется на 4 новых, его точки рекурсивно распределяются по новым листам и затем – вставка новой точки. · Процедура предназначена для удаления элемента из Q-дерева · Параметры - выходной параметр – указатель на корневой узел дерева, из которого удаляется элемент (тип PNode); - входной параметр – границы этого узла (тип TRect); - входной параметр – координаты вставляемой точки (тип TPoint); · Предусловия Указатель на дерево не должен быть пустым · Локальные переменные - CurNode – текущий квадрант (тип PNode); - ParentNode – родительский узел листа с удаляемой точкой; - DopArray – дополнительный массив, необходимый при делении листа на новые узлы (тип TArrayOfPoints); - midX, midY – координаты середины узла (тип real); - PointsInNodes, numSZ, numSV, numYZ, numYV – переменные, использующиеся при подсчете числа точек в листах (тип real); - there – индикатор наличия точки в дереве (тип boolean); - N – число точек в листе (тип integer); - i – счетчик цикла (тип integer). · Словесный алгоритм В начале своей работы функция проверяет, не является ли пустым параметр-указатель; если да – выход из подпрограммы. Если он не является листом, осуществляется цикл переходов к листу с нужными границами. Далее проверяется наличие точки в листе, и, если она там не обнаружена, процедура заканчивает свою работу; иначе происходит удаление точки из листа и последующая проверка общего числа точек в соседних листах. Если появилась возможность, соседние листы объединяются в один, старые удаляются. · Процедура предназначена для удаления всех элементов Q-дерева · Параметры - выходной параметр – указатель на узел дерева (тип PNode); · Предусловия Указатель на дерево не должен быть пустым · Словесный алгоритм В начале своей работы функция проверяет, не является ли пустым параметр-указатель; если да – выход из подпрограммы. Если он не является листом, осуществляются рекурсивные вызовы подпрограммы для каждого из его дочерних узлов; если параметр-указатель является листом, подпрограмма освобождает занятую им память и завершает свою работу. · Функция предназначена для поиска элементов Q-дерева, расположенных в заданной области карты · Параметры - входной параметр – указатель на узел дерева (тип PNode); - параметр-константа – границы этого узла (тип TRect); - параметр-константа – границы заданной области карты (тип TRect); · Функция возвращает список (тип TList) элементов дерева, расположенных в заданной области · Предусловия Указатель на дерево не должен быть пустым · Локальные переменные - NewBounds – границы нового узла, передаваемые в качестве параметра в рекурсивном вызове функции (тип TRect); - i – счетчик цикла (тип integer). · Словесный алгоритм В начале своей работы функция проверяет, не является ли пустым параметр-указатель; если да – выход из подпрограммы. Если часть площади узла находится в заданной области, осуществляются рекурсивные вызовы подпрограммы для каждого из его дочерних узлов. Для достигнутых таким образом листьев происходит проверка точек на принадлежность заданной области. · Процедура предназначена для выделения памяти и установки начальных характеристик для нового узла · Параметры - выходной параметр – указатель на узел дерева (тип PNode); · Словесный алгоритм Для нового узла, переданного в качестве параметра, выделяется память, устанавливаются начальные характеристики: тип узла (лист) и количество точек в нем (0). · Подпрограмма используется функцией вставки точек в дерево при разделении листа на 4 новых. · Процедура предназначена для копирования точек из листа в дополнительный массив · Параметры - входной параметр – указатель на узел дерева, из которого происходит копирование (тип PNode); - выходной параметр – дополнительный массив, необходимый при делении листа на новые узлы (тип TArrayOfPoints); - выходной параметр – счетчик элементов в дополнительном массиве (тип integer). · Локальные переменные - j – счетчик цикла (тип integer). · Словесный алгоритм Подпрограмма копирует значения точек из данного листа в дополнительный массив, одновременно увеличивая число его элементов, передаваемое в качестве параметра. · Подпрограмма используется функцией удаления точек из дерева при объединении 4-х листов в один. В данном модуле описаны методы работы с Q-деревом точек · Подсчет количества элементов в дереве · Отображение элементов дерева в виде точек на карте · Возможность выбора области карты для просмотра содержащихся в ней точек · Отображение точек заданной области карты в отдельном окне просмотра · Отображение координат выбранных точек Имя компонента Настраиваемые свойства OnCreate; OnKeyDown OnCreate; OnMouseMove OnMouseDown; OnMouseMove; OnMouseUp Имя компонента Настраиваемые свойства Константы · 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; - область видимости – внутри модуля; - используются для выбора и удаления точек. · Процедура предназначена для вывода изображений точек на карту · Процедура является методом класса TMainForm · Параметры - параметр-константа – точка (тип TPoint); - входной параметр – цвет изображенной точки (тип TColor); · Локальные переменные - dopX, dopY – координаты точки относительно окна просмотра (тип integer). · Словесный алгоритм Процедура вычисляет координаты отображаемой точки для каждой из карт (большой и малой) и рисует точку в виде эллипса радиусом R. · Процедура стирает предыдущее изображение на карте · Процедура является методом класса TMainForm · Параметры - входной параметр – компонент-карта (тип TImage); · Словесный алгоритм Процедура закрашивает поверхность карты цветом фона BackColor. · Процедура предназначена для поиска и вывода изображений точек дерева в заданной области карты · Процедура является методом класса TMainForm · Параметры - параметр-константа – указатель на узел дерева (тип PNode); - параметр-константа – границы заданной области (тип TRect); · Локальные переменные - FindedPoints – список найденных точек (тип TList); - dopPoint – точка из списка (тип TPoint); - i –счетчик цикла (тип integer). · Словесный алгоритм Процедура создает пустой список, копирует туда точки дерева, найденные в заданной области, и выводит их изображения на карты. · Процедура предназначена для задания начальных координат областей и точек · Процедура является методом класса TMainForm · Параметры - входной параметр – объект, сгенерировавший событие (тип TObject) · Словесный алгоритм Процедура устанавливает границы главного квадранта и выделенной области, начальные координаты для текущей и выбранной точек. · Процедура предназначена для получения начальных координат указателя мыши перед началом перетаскивания выделяющего окна · Процедура является методом класса TMainForm · Параметры - входной параметр – объект, сгенерировавший событие (тип TObject); - входной параметр – индикатор нажатой кнопки мыши (тип TMouseButton); - входной параметр – индикатор нажатой клавиши (тип TShiftState); - входные параметры – координаты указателя мыши (тип integer) · Словесный алгоритм Координаты указателя записываются в глобальные переменные X0 и Y0. Индикатору перетаскивания drag присваивается true. · Процедура предназначена для установки значения соответствующего индикатора при окончании перетаскивания окна выделения · Процедура является методом класса TMainForm · Параметры - входной параметр – объект, сгенерировавший событие (тип TObject); - входной параметр – индикатор нажатой кнопки мыши (тип TMouseButton); - входной параметр – индикатор нажатой клавиши (тип TShiftState); - входные параметры – координаты указателя мыши (тип integer) · Словесный алгоритм Индикатору перетаскивания drag присваивается false. · Процедура предназначена для перемещения окна выделения по малой карте и вывода на карту изображений точек из выделенной области · Процедура является методом класса TMainForm · Параметры - входной параметр – объект, сгенерировавший событие (тип TObject); - входной параметр – индикатор нажатой клавиши (тип TShiftState) - входные параметры – координаты указателя мыши (тип integer) · Предусловия Индикатор перетаскивания должен быть равен true. · Локальные переменные - newLeft, newTop – новые координаты окна выделения (тип integer) · Словесный алгоритм Процедура вычисляет новые координаты окна выделения и области просмотра с использованием глобальных переменных X0 и Y0; затем осуществляет поиск и вывод на карту изображений точек из новой области с помощью процедуры DrawRegion. · Процедура предназначена для отображения координат выделяемых точек в строке состояния и выделения их изображений на карте · Процедура является методом класса TMainForm · Параметры - входной параметр – объект, сгенерировавший событие (тип TObject); - входной параметр – индикатор нажатой клавиши (тип TShiftState); - входные параметры – координаты указателя мыши (тип integer) · Локальные переменные - Point – выделенная точка (тип TPoint); - Rect – область поиска точки в дереве (тип TRect); - str – строка с координатами выбранной точки (тип string); - List – список точек, найденных в области вблизи указателя мыши · Словесный алгоритм Подпрограмма выводит в строку состояния координаты движущегося указателя мыши и осуществляет проверку того, наведен ли он на точку, путем поиска точек дерева в области вокруг указателя. Если таковые имеются, изображение первой из них перерисовывается соответствующим цветом. · Процедура предназначена для добавления точки в дерево и «запоминания» координат выбранной точки · Процедура является методом класса TMainForm · Параметры - входной параметр – объект, сгенерировавший событие (тип TObject) · Локальные переменные - Point – новая либо выбранная точка (тип TPoint); - str – строка с координатами выбранной точки (тип string); - i, j – координаты точки относительно окна просмотра (тип integer) · Словесный алгоритм Подпрограмма получает координаты новой (или выбранной) точки из строки состояния. Затем, если программа находится в режиме добавления точек, вставляет в дерево новую точку; в зависимости от результата функции вставки, увеличивает счетчик точек на единицу и перерисовывает изображение. В режиме выбора точек процедура записывает в глобальную переменную координаты выбранной точки и перекрашивает ее на карте соответствующим цветом. Координаты выбранной точки выводятся в строку состояния. · Процедура предназначена для удаления выбранной точки из дерева · Процедура является методом класса TMainForm · Параметры - входной параметр – объект, сгенерировавший событие (тип TObject) · Словесный алгоритм Подпрограмма удаляет выбранную точку из дерева; затем, если необходимо, перерисовывает просматриваемую область карты. · Процедура предназначена для удаления всех точек из дерева · Процедура является методом класса TMainForm · Параметры - входной параметр – объект, сгенерировавший событие (тип TObject) · Словесный алгоритм Подпрограмма удаляет все точки из дерева, «стирает» изображение с карты и устанавливает «пустые » координаты для выбранной и текущей точек. · Процедура осуществляет перемещение окна выделения при нажатии клавиш · Процедура является методом класса 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; Point: TPoint): boolean; procedure DeletePoint(var Node: PNode; Bounds: TRect; Point: TPoint); 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; Point: TPoint): boolean; 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 Point.X < midX then if Point.Y < midY then begin CurNode:= CurNode^.SZ; X2:= midX; Y2:= midY; end else begin CurNode:= CurNode^.YZ; Y1:= midY; X2:= midX; end else if Point.Y < midY then 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 = Point.X)and(CurNode^.Points[i].Y = Point.Y) then begin Result:= false; Exit; end; //Если массив не заполнен, вставляем точку... if CurNode^.PointsCount < M then begin CurNode^.Points[CurNode^.PointsCount + 1]:= Point; 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, Point); end; end; //УДАЛЕНИЕ ТОЧКИ ИЗ ДЕРЕВА =================================================== procedure DeletePoint(var Node: PNode; Bounds: TRect; Point: TPoint); 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 Point.X < midX then if Point.Y < midY then begin CurNode:= CurNode^.SZ; X2:= midX; Y2:= midY; end else begin CurNode:= CurNode^.YZ; Y1:= midY; X2:= midX; end else if Point.Y < midY then 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 = Point.X)and(CurNode^.Points[i].Y = Point.Y) then 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 Point: TPoint; PointColor: TColor); 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 Point: TPoint; PointColor: TColor); var dopX, dopY: integer; begin //В большом окне... with Point do 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 Point: TPoint; 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 Point.X:= X + Query.X1; Point.Y:= Y + Query.Y1; 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 Point:= TPoint(List[0]^); Panels[3].Text:= 'Точка ' + FloatToStr(Point.X) + '; ' + FloatToStr(Point.Y); //"Подсветка" точки---------------------------------------------- if Pixels[round(Point.X - Query.X1),round(Point.Y - Query.Y1)] <> 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 Point: TPoint; str: string[30]; i, j: integer; begin Point.X:= StrToInt(copy(StatusBar.Panels[0].Text, 4, 10)); Point.Y:= StrToInt(copy(StatusBar.Panels[1].Text, 4, 10)); ifSBtnPoints.Downthen //В режиме добавления точек ----------------------- begin //Добавление точки в дерево if InsertPoint(Tree, mainBounds, Point) then PointCount:= PointCount + 1; ClearBackground(MaxImage); ClearBackground(MinImage); //Перерисовка области просмотра DrawRegion(Tree, Query); DrawRegion(Tree, mainBounds); StatusBar.Panels[2].Text:= 'Количество точек: ' + IntToStr(PointCount); end else begin if (Point.X = SelectedPoint.X)and(Point.Y = SelectedPoint.Y) then Exit; i:= round(Point.X - Query.X1); j:= round(Point.Y - Query.Y1); 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.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||