Реферат: Структура данных программного комплекса "Q-дерево"
/>/>Реферат
Представляемый документ содержит:
52 страницы текста и список из двухисточников.
Объектом исследования являетсяструктура данных «Q-дерево».
Цель работы состоит в созданиипрограммного комплекса, обеспечивающего работу со структурой данных «Q-дерево», представленной в видемодели. Методы, используемые при разработке, – язык программирования высокогоуровня Object Pascal. Созданный программный продуктобеспечивает выполнение всех требований технического задания.
Содержание
Введение
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-деревьями. Актуальностьразработки программного продукта состоит в увеличении скорости работы смножествами. Программный продукт должен быть разработан на языкепрограммирования высокого уровня Object Pascal, использовать принципыобъектно-ориентированного программирования и структурный подход к решениюпоставленных задач.
Результатом выполнения курсовойработы должен стать готовый программный продукт, отвечающий всем требованиямтехнического задания.
/>/>/>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 Гб;
− видеоадаптер AGP 8X;
− клавиатура;
− манипулятортипа “мышь”.
1.5 Требования к информационной и программнойсовместимостиДля работы программы необходимаоперационная система Microsoft Windows XP Professional 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 Модуль UnitModel2.1.1 Назначение
Данный модуль представляет собойреализацию модели структуры данных «Q-деревоточек».
2.1.2 Функциональные требования, реализуемые модулем· Возможность добавления элементовв дерево
· Удаление элементов из дерева
· Очистка дерева
· Поиск точек в заданнойпрямоугольной области карты.
2.1.3 Глобальные переменные и константы модуляКонстанты
· М = 3 – максимальное число точек влисте;
- тип – целый;
- областьвидимости – внутри и вне модуля;
- используетсяв операциях вставки и удаления элементов дерева для проверки числа точек влистьях.
2.1.4 Подпрограммы модуля/>2.1.4.1 Функция InsertPoint
· Функцияпредназначена для вставки нового элемента в Q-дерево
· Параметры
- выходнойпараметр – указатель на узел дерева, в которое вставляется элемент (тип PNode);
- входнойпараметр – границы этого узла (тип TRect);
- входнойпараметр – координаты вставляемой точки (тип TPoint);
· Функциявозвращает логическое значение (тип boolean),указывающее на изменение количества элементов в дереве
· Локальныепеременные
- 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 Модуль UnitMainForm2.2.1 НазначениеВ данном модуле описаны методыработы с Q-деревом точек
2.2.2 Функциональные требования, реализуемые модулем· Подсчетколичества элементов в дереве
· Отображениеэлементов дерева в виде точек на карте
· Возможностьвыбора области карты для просмотра содержащихся в ней точек
· Отображениеточек заданной области карты в отдельном окне просмотра
· Отображениекоординат выбранных точек
2.2.3 Используемые компоненты№Имя
компонента
КлассНастраиваемые
свойства
Значения Обработанные события 1 MainForm TMainForm BorderStyle bsSingleOnCreate;
OnKeyDown
Caption Q-дерево KeyPreview True 2 MaxImage TImage – –OnCreate;
OnMouseMove
3 MinImage TImage – – – 4 ShapeView TShape Brush Style bsClearOnMouseDown;
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)
· Локальныепеременные
- Point – выделенная точка (тип TPoint);
- Rect – область поиска точки в дереве(тип TRect);
- str – строка с координатамивыбранной точки (тип string);
- List – список точек, найденных вобласти вблизи указателя мыши
· Словесныйалгоритм
Подпрограмма выводит в строкусостояния координаты движущегося указателя мыши и осуществляет проверку того,наведен ли он на точку, путем поиска точек дерева в области вокруг указателя.Если таковые имеются, изображение первой из них перерисовываетсясоответствующим цветом.
/>2.1.5.9 Процедура MaxImageClick· Процедурапредназначена для добавления точки в дерево и «запоминания» координат выбраннойточки
· Процедураявляется методом класса TMainForm
· Параметры
- входнойпараметр – объект, сгенерировавший событие (тип TObject)
· Локальныепеременные
- Point – новая либо выбранная точка(тип TPoint);
- 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.
Приложение
Текст программы
programQtree;
uses Forms,
UnitMainForm in 'UnitMainForm.pas' {MainForm},
UnitModel in 'UnitModel.pas';
{$R*.res}
begin
Application.Initialize;
Application.CreateForm(TMainForm, MainForm);
Application.Run;
end.
unitUnitModel;
interface
usesClasses;
const M = 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;
functionInsertPoint(var Node: PNode; Bounds: TRect; Point: TPoint): boolean;
procedureDeletePoint(var Node: PNode; Bounds: TRect; Point: TPoint);
procedureClearTree(var Node: PNode);
functionFind(Node: PNode; const Bounds, Rect: TRect): TList;
implementation
//Установкахарактеристик нового листа =======================================
procedureSetProperties(var ChildNode: PNode);
begin
New(ChildNode);
ChildNode^.Kind:=nkLeaf;
ChildNode^.PointsCount:= 0; //вмассиве нет точек
end;
//Копированиеточек из листа в дополнительный массив =========================
procedureCopyPoints(Node: PNode; var DopArray: TArrayOfPoints; var i: integer);
varj: integer;
begin
forj:=1 to Node^.PointsCount do
begin
DopArray[i]:= Node^.Points[j];
inc(i);
end;
end;
//ВСТАВКА ТОЧКИВ ДЕРЕВО =====================================================
functionInsertPoint(var Node: PNode; Bounds: TRect; Point: TPoint): boolean;
varCurNode: PNode; //текущий квадрант
DopArray: TArrayOfPoints; //дополнительный массив (когда делим узел)
i: integer;
midX, midY: real;
NewBounds: TRect;
begin
ifNode = nil then
begin
New(Node);
Node^.Kind:= nkLeaf;
Node^.PointsCount:= 0;
end;
CurNode:=Node;
Result:=true;
withBounds 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;
//Собственновставка----------------------------------------------------------
//Проверить,есть ли место в массиве точек и нет ли уже там новой:
fori:=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;
//Если массив незаполнен, вставляем точку...
ifCurNode^.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);
//Распределениеточек по узлам
for i:=1 to M do
withBounds 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;
//УДАЛЕНИЕ ТОЧКИИЗ ДЕРЕВА ===================================================
procedureDeletePoint(var Node: PNode; Bounds: TRect; Point: TPoint);
varCurNode, ParentNode: PNode;
DopArray: TArrayOfPoints;
midX, midY, PointsInNodes, numSZ, numSV, numYZ, numYV: real;
there: boolean;
i, N: integer;
begin
ifNode = nil then
Exit;
CurNode:=Node;
ParentNode:=CurNode;
withBounds 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;
fori:=1 to M do
if(CurNode^.Points[i].X = Point.X)and(CurNode^.Points[i].Y = Point.Y) then
begin
there:= true;
break;
end;
//Удаляем точку(либо выходим, если таковой не имеется)
ifthere then
begin
CurNode^.Points[i]:= CurNode^.Points[N];
CurNode^.PointsCount:= CurNode^.PointsCount — 1;
end
elseExit;
ifNode^.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;
if PointsInNodes <= M then
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;
//УДАЛЕНИЕДЕРЕВА ============================================================
procedureClearTree(var Node: PNode);
begin
ifNode = nil then
Exit;
ifNode^.Kind = nkBranch then
begin
ClearTree(Node^.SZ);
ClearTree(Node^.SV);
ClearTree(Node^.YZ);
ClearTree(Node^.YV);
end;
Dispose(Node);
Node:=nil;
end;
//ПОИСК ТОЧЕК ВЗАДАННОЙ ОБЛАСТИ =============================================
functionFind(Node: PNode; const Bounds, Rect: TRect): TList;
varNewBounds: TRect;
i:integer;
begin
Result:=TList.Create;
ifNode = nil then
Exit;
withBounds 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.
unitUnitMainForm;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, ExtCtrls, StdCtrls, UnitModel, ComCtrls, Buttons;
const Xmax = 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}
constK = 10.56; //масштаб (MaxImage.Width/MinImage.Width)
R =3; //радиус точки на форме
LightColor = clLime; //цветподсветки точек
SelectColor = clRed; //цветвыделенной точки
BackColor = clWhite; //цвет фона
varTree: PNode;
X0, Y0: integer;
drag:boolean = false; //флажокперетаскивания окна просмотра
PointCount: integer = 0; //числоточек в дереве
mainBounds, Query: TRect; //главныйквадрант и окно просмотра
LightPoint,SelectedPoint: TPoint;
//Отрисовкаточки ============================================================
procedureTMainForm.DrawPoint(const Point: TPoint; PointColor: TColor);
vardopX, dopY: integer;
begin
//Вбольшом окне...
withPoint 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;
//«Очистка»фона=============================================================
procedureTMainForm.ClearBackground(Image: TImage);
begin
withImage.Canvas do
begin
Brush.Style:= bsSolid;
Brush.Color:= BackColor;
Rectangle(-1,-1,Image.Width + 1,Image.Height + 1);
end;
end;
//Отрисовкапросматриваемой области ==========================================
procedureTMainForm.DrawRegion(const Node: PNode; const Bounds: TRect);
varFindedPoints: TList;
dopPoint: TPoint;
i: integer;
begin
FindedPoints:=TList.Create;
withFindedPoints do
begin
Assign(Find(Node, mainBounds, Bounds), laOr);
ifCapacity <> 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;
//Заданиеначальных координат областей и точек ===============================
procedureTMainForm.FormCreate(Sender: TObject);
begin
withmainBounds do
begin
X1:= 0;
Y1:= 0;
X2:= Xmax;
Y2:= Xmax;
end;
withQuery do
begin
X1:= 0;
Y1:= 0;
X2:= MaxImage.Width;
Y2:= MaxImage.Width;
end;
withLightPoint do
begin
X:= -4;
Y:= -4;
end;
withSelectedPoint do
begin
X:= -3;
Y:= -3;
end;
end;
//НАВИГАЦИЯ ВМАЛОМ ОКНЕ =====================================================
procedureTMainForm.ShapeViewMouseDown(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
begin
X0:=X;
Y0:=Y;
drag:=true;
end;
procedureTMainForm.ShapeViewMouseUp(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
begin
drag:=false;
end;
procedureTMainForm.ShapeViewMouseMove(Sender: TObject; Shift: TShiftState;
X, Y: Integer);
varnewLeft, newTop: integer;
begin
ifdrag 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;
//Отображениекоординат точек в строке состояния =============================
procedureTMainForm.MaxImageMouseMove(Sender: TObject; Shift: TShiftState;
X,Y: Integer);
varPoint: TPoint;
Rect: TRect;
str: string[30];
List: TList;
begin
ifSBtnCursor.Down then
MaxImage.Cursor:= crDefault
elseMaxImage.Cursor:= crCross;
withStatusBar 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)] =
LightColorthen
if (X = SelectedPoint.X)and(Y = SelectedPoint.Y) then
DrawPoint(LightPoint, SelectColor)
else DrawPoint(LightPoint, clBlack);
end;
end;
end;
//Клик побольшому окну ======================================================
procedureTMainForm.MaxImageClick(Sender: TObject);
varPoint: 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));
if SBtnPoints.Down then //В режимедобавления точек -----------------------
begin
//Добавление точки в дерево
ifInsertPoint(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
//«Запомнить»выбранную точку -------------------------------------
with SelectedPoint do
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;
//Удалениеточки =============================================================
procedureTMainForm.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;
//Удалениедерева ============================================================
procedureTMainForm.ButtonClearClick(Sender: TObject);
begin
ClearTree(Tree);
ClearBackground(MaxImage);
ClearBackground(MinImage);
DrawRegion(Tree,mainBounds);
PointCount:=0;
withStatusBar 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;
//Перемещениеокошка с помощью клавиш ========================================
procedureTMainForm.FormKeyDown(Sender: TObject; var Key: Word;
Shift: TShiftState);
constdif = 4;
begin
drag:=true;
withShapeView do
begin
X0:= Left + round(Width/2);
Y0:= Top + round(Height/2);
end;
ifKey = VK_UP then
ShapeViewMouseMove(ShapeView, Shift, X0, Y0 — dif)
else
ifKey = 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.