Удаление элемента производится путем выделения точки с помощью мыши в окне просмотра в режиме выделения точек и щелчка по кнопке «Удалить точку» (рис. 2)
Рис. 2
Результат: удаление точки из дерева и его перерисовка; уменьшение количества точек в дереве на единицу.
Очистка дерева
Очистка дерева (удаление всех элементов) производится щелчком по кнопке «Удалить все» (рис. 3)
Рис. 3
Результат: удаление всех элементов дерева и соответствующая перерисовка изображений
Возможность выбора прямоугольной области карты для просмотра содержащихся в ней точек, поиск точек в заданной прямоугольной области карты
Выбор области просмотра осуществляется перемещением окна выделения с помощью мыши или клавиш (рис. 4)
Рис. 4
Результат: перемещение окна выделения, поиск и отрисовка точек, находящихся в выделенной области карты.
Отображение элементов дерева в виде точек на карте, отображение координат выбираемых точек
Выбор точки производится с помощью щелчка левой кнопкой мыши по точке с нужными координатами в режиме выбора точек (рис. 5)
Рис. 5
Результат: отображение координат выбранной точки в строке состояния; перерисовка соответствующим цветом ее изображения в окне просмотра.
Отображение точек заданной области карты в отдельном окне просмотра, отображение координат выбираемых точек
Для получения координат точки без ее выделения достаточно навести указатель мыши на ее изображение в окне просмотра (рис. 6)
Рис. 6
Результат: отображение координат точки в строке состояния без ее выбора; перерисовка соответствующим цветом ее изображения в окне просмотра.
Рабочий проект
Модуль UnitModel
Назначение
Данный модуль представляет собой реализацию модели структуры данных «Q-дерево точек».
2.1.2 Функциональные требования, реализуемые модулем
· Возможность добавления элементов в дерево
· Удаление элементов из дерева
· Очистка дерева
· Поиск точек в заданной прямоугольной области карты.
Глобальные переменные и константы модуля
Константы
· М = 3 – максимальное число точек в листе;
- тип – целый;
- область видимости – внутри и вне модуля;
- используется в операциях вставки и удаления элементов дерева для проверки числа точек в листьях.
Подпрограммы модуля
Функция InsertPoint
· Функция предназначена для вставки нового элемента в Q-дерево
· Параметры
- выходной параметр – указатель на узел дерева, в которое вставляется элемент (тип PNode);
- входной параметр – границы этого узла (тип TRect);
- входной параметр – координаты вставляемой точки (тип TPoint);
· Функция возвращает логическое значение (тип boolean), указывающее на изменение количества элементов в дереве
· Локальные переменные
- CurNode – текущий квадрант (тип PNode);
- DopArray – дополнительный массив, необходимый при делении листа на новые узлы (тип TArrayOfPoints);
- midX, midY – координаты середины узла (тип real);
- NewBounds – границы нового узла, передаваемые в качестве параметра в рекурсивном вызове функции (тип TRect);
- i – счетчик цикла (тип integer).
· Словесный алгоритм
В начале своей работы функция проверяет, не является ли пустым параметр-указатель; если да, то для него выделяется память, устанавливаются начальные значения полей и вставляется новый элемент. Если он не является листом, осуществляется цикл переходов к листу с нужными границами. Далее проверяется число элементов в листе, и, если оно меньше допустимого, туда вставляется новая точка; иначе этот лист разделяется на 4 новых, его точки рекурсивно распределяются по новым листам и затем – вставка новой точки.
Процедура 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).
· Словесный алгоритм
В начале своей работы функция проверяет, не является ли пустым параметр-указатель; если да – выход из подпрограммы. Если он не является листом, осуществляется цикл переходов к листу с нужными границами. Далее проверяется наличие точки в листе, и, если она там не обнаружена, процедура заканчивает свою работу; иначе происходит удаление точки из листа и последующая проверка общего числа точек в соседних листах. Если появилась возможность, соседние листы объединяются в один, старые удаляются.
Процедура ClearTree
· Процедура предназначена для удаления всех элементов Q-дерева
· Параметры
- выходной параметр – указатель на узел дерева (тип PNode);
· Предусловия
Указатель на дерево не должен быть пустым
· Словесный алгоритм
В начале своей работы функция проверяет, не является ли пустым параметр-указатель; если да – выход из подпрограммы. Если он не является листом, осуществляются рекурсивные вызовы подпрограммы для каждого из его дочерних узлов; если параметр-указатель является листом, подпрограмма освобождает занятую им память и завершает свою работу.
Функция Find
· Функция предназначена для поиска элементов Q-дерева, расположенных в заданной области карты
· Параметры
- входной параметр – указатель на узел дерева (тип PNode);
- параметр-константа – границы этого узла (тип TRect);
- параметр-константа – границы заданной области карты (тип TRect);
· Функция возвращает список (тип TList) элементов дерева, расположенных в заданной области
· Предусловия
Указатель на дерево не должен быть пустым
· Локальные переменные
- NewBounds – границы нового узла, передаваемые в качестве параметра в рекурсивном вызове функции (тип TRect);
- i – счетчик цикла (тип integer).
· Словесный алгоритм
В начале своей работы функция проверяет, не является ли пустым параметр-указатель; если да – выход из подпрограммы. Если часть площади узла находится в заданной области, осуществляются рекурсивные вызовы подпрограммы для каждого из его дочерних узлов. Для достигнутых таким образом листьев происходит проверка точек на принадлежность заданной области.
Процедура SetProperties
· Процедура предназначена для выделения памяти и установки начальных характеристик для нового узла
· Параметры
- выходной параметр – указатель на узел дерева (тип PNode);
· Словесный алгоритм
Для нового узла, переданного в качестве параметра, выделяется память, устанавливаются начальные характеристики: тип узла (лист) и количество точек в нем (0).
· Подпрограмма используется функцией вставки точек в дерево при разделении листа на 4 новых.
Процедура CopyPoints
· Процедура предназначена для копирования точек из листа в дополнительный массив
· Параметры
- входной параметр – указатель на узел дерева, из которого происходит копирование (тип PNode);
- выходной параметр – дополнительный массив, необходимый при делении листа на новые узлы (тип TArrayOfPoints);
- выходной параметр – счетчик элементов в дополнительном массиве (тип integer).
· Локальные переменные
- j – счетчик цикла (тип integer).
· Словесный алгоритм
Подпрограмма копирует значения точек из данного листа в дополнительный массив, одновременно увеличивая число его элементов, передаваемое в качестве параметра.
· Подпрограмма используется функцией удаления точек из дерева при объединении 4-х листов в один.
Модуль UnitMainForm
Назначение
В данном модуле описаны методы работы с Q-деревом точек
2.2.2 Функциональные требования, реализуемые модулем
· Подсчет количества элементов в дереве
· Отображение элементов дерева в виде точек на карте
· Возможность выбора области карты для просмотра содержащихся в ней точек
· Отображение точек заданной области карты в отдельном окне просмотра
· Отображение координат выбранных точек
Используемые компоненты
| № | Имя компонента | Класс | Настраиваемые свойства | Значения | Обработанные события | |
| 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 | – | – | – |
Дата: 2019-07-24, просмотров: 219.
