Разработка класса "Квадродерево" для реализации операций с квадродеревьями на Object Pascal - Курсовая работа

Для того чтобы объявить класс на Turbo Pascal"е необходимо воспользоваться ключевым словом Object. Так как класс всегда является типом, делать это можно лишь в Type части программы: Type Легко заметить, что поля и методы (общее для них название - члены класса) объявляются очень похоже на поля записи и обычные процедуры/функции. Соответственно, доступ к полям объекта некоторого класса производится аналогично доступу к полям записи: Object1.V:= Object2.A;Квадродерево (квадротомическое дерево) - структура данных, используемая для представления двумерных пространственных данных. Следуя [7], под двумерным изображением понимается массив элементов изображения (пикселов). Если каждый из пикселов имеет только два состояния - черный или белый (подсвечен или нет), то изображение называется монохромным. Больший квадрант становится узлом более высокого иерархического уровня квадродерева, а меньшие квадранты появляются на более низких уровнях. Корневой узел соответствует изображению в целом и имеет четыре дочерних узла, которые ассоциируются с четырьмя квадрантами исходного изображения (обозначаемыми NW - северо-западный, NE - северо-восточный, SW - юго-западный, SE - юго-восточный).4: (a) первый этап разбиения (b) второй этап разбиния (c) третий этап разбиения (d) изображение полностью разбито На каждом этапе построения квадродерева изображение разбивается на четыре квадранта и каждому присваивается одно из следующих значений В показанном на рисунках частном случае северо-западный NW-квадрант обозначен белым квадратом, а остальные три - серыми кругами (рисунок 5). На очередном этапе серые квадранты снова подвергаются разбиению (на рисунке 3b для простоты показано лишь разбиение SW-квадранта). Как видно по рисунку 3b SW-квадрант на этом этапе содержит два белых, один черный и один серый подквадранты.Если узел не является листовым, то он пропускается и просматривается его первый дочерний узел. Если этот дочерний узел не листовой, то он пропускается и происходит переход к его первый дочерний узел и т.д.Большинство приложений квадро деревьев к данным было сделано для изображений (Klinger, Dyer, 1976), но были проведены также современные алгоритмические разработки, которые дали результаты, сходные с теми, что используются при обработке географических данных. Сюда входят расчеты площадей, центороидные определения, распознавание образов [4], классификация изображений, оверлейные операции над изображениями, выявление связанных компонент, определение соседства [1], преобразование расстояний [7], разделение изображений, сглаживание данных и усиление краевых эффектов [4]. Вследствие этих преимуществ отдельные исследователи предложили использовать квадротомические деревья для хранения географических данных. Компактность квадродерева целиком зависит от изображения. Изображение с большими областями, окрашенными в один цвет представляются очень компактно, в то время как изображение, в котором все пикселы имеют разные цвета сводит на нет все преимущества квадродерева [10].Главный недостаток квадродеревьев состоит в том, что почти невозможно сравнить два изображения, которые отличаются, например, лишь поворотом. Алгоритмы поворота квадротомированного изображения ограничиваются лишь поворотами на углы, кратные 90 градусам. Хотя квадродеревья имеют массу плюсов в Геоинформационных-приложениях, их распространение в других областях сдерживается их недостатками.Left, Top, Bottom, Right: Integer; constructor Create(R: TRECT; L: Integer; Hint: string; F: TQSCAN); begin for x := 1 to XMAX do begin for y := 1 to YMAX do for x := R.Left to R.Right do for y := R.Top to R.Bottom do begin if M[x, y] = 0 then begin if (R.Right >= R.Left) and (R.Bottom >= R.Top) then beginИспользование квадродерева продемонстрировано на классической задаче разбора бинарной матрицы N на M. Сначала выводится матрица, потом выводятся данные по ходу формирования дерева, затем выводится само дерево. Квадрант помечается цифрой 2, если он содержит и нули и единицы; при этом продолжается дальнейшее разбиение этого квадранта.

Оглавление

Введение

1. Общие понятия

2. Пример квадродерева

3. Визуализация квадротомированного изображения

4. Достоинства квадродерева

5. Недостатки квадродерева

6. Результаты

Вывод

Список источников и литературы

Для того чтобы объявить класс на Turbo Pascal"е необходимо воспользоваться ключевым словом Object. Так как класс всегда является типом, делать это можно лишь в Type части программы: Type

Class1 = Object

{список полей} A: Byte; V: Real; {список методов} Procedure Nothing(Var K: Byte); End;

Легко заметить, что поля и методы (общее для них название - члены класса) объявляются очень похоже на поля записи и обычные процедуры/функции. Объекты класса объявляются так же, как и обычные переменные: Var

Object1, Object2: Class1;

Соответственно, доступ к полям объекта некоторого класса производится аналогично доступу к полям записи: Object1.V:= Object2.A;

Обращение к методам класса производится аналогичным образом: Object1.Nothing(Object1.A);

Одной из наиболее изученных и хорошо зарекомендовавших себя структур данных для представления двумерных изображений является квадротомическое дерево или квадродерево (quadtree). Благодаря естественной иерархической структуре и способу организации квадродеревья сочетают в себе значительную экономию объемов памяти с эффективностью доступа к элементам изображения. Идеология квадродеревьев применяется не только для представления растровых изображений, но и используется для эффективной организации больших баз любых пространственных данных, состоящих как из растровых, так и векторных изображений.

program Project1;

uses Crt;

const

XMAX = 8;

YMAX = 8;

type

TMATRIX = array[1..XMAX, 1..YMAX] of Byte;

TRECT = record

Left, Top, Bottom, Right: Integer;

end;

TQSCAN = function(R: TRECT): Byte;

PQTREE = ^TQTREE;

TQTREE = object

Max: Byte;

Rect: TRECT;

NW, NE, SW, SE: PQTREE;

constructor Create(R: TRECT; L: Integer; Hint: string; F: TQSCAN);

procedure View(Pad: Integer; S: string);

destructor Destroy;

end;

var

M: TMATRIX;

Rect: TRECT;

Root: PQTREE;

procedure FILLMATRIX;

var x, y: Integer;

begin

Randomize;

for x := 1 to XMAX do for y := 1 to YMAX do if Random(6) > 0 then

M[x, y] := 1 else

M[x, y] := 0;

end;

procedure WRITEMATRIX;

var x, y: Integer;

begin for x := 1 to XMAX do begin for y := 1 to YMAX do

Write(M[x, y], " ");

WRITELN;

end;

end;

{$F } function SCANMATRIX(R: TRECT): Byte;

var x, y: Integer;

WHITEFINDED, BLACKFINDED: Boolean;

begin

SCANMATRIX := 0;

WHITEFINDED := False;

BLACKFINDED := False;

for x := R.Left to R.Right do for y := R.Top to R.Bottom do begin if M[x, y] = 0 then

WHITEFINDED := True;

if M[x, y] = 1 then

BLACKFINDED := True;

if WHITEFINDED and BLACKFINDED then

Break;

end;

if WHITEFINDED and BLACKFINDED then

SCANMATRIX := 2 else if BLACKFINDED then

SCANMATRIX := 1 else if WHITEFINDED then

SCANMATRIX := 0;

end;

{$F-} constructor TQTREE.Create(R: TRECT; L: Integer; Hint: string; F: TQSCAN);

var dx, dy: Integer;

TMPR: TRECT;

begin if (R.Right >= R.Left) and (R.Bottom >= R.Top) then begin

Self.Max := F(R);

WRITELN("[", R.Left, ",", R.Right, "], [", R.Top, ",", R.Bottom, "]. Level=", L, ", ", Hint, " > ", Self.Max);

if Self.Max < 2 then begin

Self.NW := nil;

Self.NE := nil;

Self.SW := nil;

Self.SE := nil;

end else begin dx := (R.Right - R.Left) div 2;

dy := (R.Bottom - R.Top) div 2;

{NW}

TMPR.Left := R.Left;

TMPR.Right := R.Left dx;

TMPR.Top := R.Top;

TMPR.Bottom := R.Top dy;

Self.NW := New(PQTREE, Create(TMPR, L 1, "NW", F));

{NE}

TMPR.Left := R.Left dx 1;

TMPR.Right := R.Right;

TMPR.Top := R.Top;

TMPR.Bottom := R.Top dy;

Self.NE := New(PQTREE, Create(TMPR, L 1, "NE", F));

{SW}

TMPR.Left := R.Left;

TMPR.Right := R.Left dx;

TMPR.Top := R.Top dy 1;

TMPR.Bottom := R.Bottom;

Self.SW := New(PQTREE, Create(TMPR, L 1, "SW", F));

{SE}

TMPR.Left := R.Left dx 1;

TMPR.Right := R.Right;

TMPR.Top := R.Top dy 1;

TMPR.Bottom := R.Bottom;

Self.SE := New(PQTREE, Create(TMPR, L 1, "SE", F));

end;

end;

end;

procedure TQTREE.View(Pad: Integer; S: string);

var i: Integer;

begin if @Self nil then begin

Self.NW^.View(Pad 5, "NW");

Self.NW^.View(Pad 5, "NE");

for i := 1 to Pad do

Write("-");

WRITELN(S, ":", Self.Max);

Self.NW^.View(Pad 5, "SW");

Self.NW^.View(Pad 5, "SE");

end;

end;

destructor TQTREE.Destroy;

begin if @Self nil then begin if Self.NW nil then

Dispose(Self.NW, Destroy);

if Self.NE nil then

Dispose(Self.NE, Destroy);

if Self.SW nil then

Dispose(Self.SW, Destroy);

if Self.SE nil then

Dispose(Self.SE, Destroy);

end;

end;

begin

CLRSCR;

FILLMATRIX;

Writeln("Source matrix: ");

WRITEMATRIX;

READLN;

Writeln("Processing: ");

Rect.Left := 1;

Rect.Top := 1;

Rect.Right := XMAX;

Rect.Bottom := YMAX;

Root := New(PQTREE, Create(Rect, 1, "ROOT", SCANMATRIX));

READLN;

Writeln("Tree: ");

Root^.View(1, "ROOT");

READLN;

Dispose(Root, Destroy);

end.Использование квадродерева продемонстрировано на классической задаче разбора бинарной матрицы N на M.

Для примера в программе используется матрица 8 на 8, которая заполняется случайным образом.

Сначала выводится матрица, потом выводятся данные по ходу формирования дерева, затем выводится само дерево.

Квадрант помечается цифрой 2, если он содержит и нули и единицы; при этом продолжается дальнейшее разбиение этого квадранта.

Квадрант помечается цифрой 1 или цифрой 0, если он содержит только единицы или только нули соответственно.

Пометки обозначают: Root - корень, NW - северо-запад, NE - северо-восток, SW - юго-запад, SE - юго-восток.

TQTREE - класс

TMATRIX, TRECT и TQSCAN - это обычные типы, которые описывают другие вспомогательные структуры

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

Литература

1. Кошкарев А.В., Тикунов В.С. Геоинформатика. Москва, Картгеоцентр-Геоиздат, 1993. С. 55-57.

2. Tobler, W., Zi-tan Chen. (1986) A quadtree for global Information Storage. - "Geographical Analysis", 1986, October, Vol. 18, No. 4. Существует перевод: Тоблер В., Зи-тан Чен. Квадротомическое дерево для глобального хранения информации. // Картография. Вып. 4. Геоинформационные системы: Сб. перев. статей/Сост., ред и предисл. А.М. Берлянт и В.С. Тикунов. - М.: Картгеоцентр - Геоиздат, 1994. C. 89-101.

3. Mark D.M. (1986) Construction of Quadtrees and Octtrees from Reaster Data. A new algorithm Based on Run-Encoding. - "The Australian Computer Journal", 1986, August, Vol. 18, No. 3, p 115-119. Существует перевод: Марк Д.М. Построение квадротомических и октотомических деревьев на базе растровых данных: новый алгоритм быстрого кодирования. // Картография. Вып. 4. Геоинформационные системы: Сб. перев. статей/Сост., ред и предисл. А.М. Берлянт и В.С. Тикунов. - М.: Картгеоцентр - Геоиздат, 1994. C. 102-109.

4. Bell, S.B., B.M. Diaz, and F.C. Holroyd. (1988) Digital Image Processing in Remote Sensing. Capturing Image Syntax using Tesseral addressing and arithmetic. Taylor & Francis Ltd: USA.

5. Hunter G.M. and Stiglitz K. (1979) IEEE Transactions on Pattern Analysis and Machine Intelligence. Operations on Images Using Quad Trees. April: 145-153.

6. Samet,H. (1990) The Design and Analysis of Spatial Data Structures. Addison-Wesley Publishing Company, Inc: Reading.

7. Samet H.(1981) Computer Graphics and Image processing. Neighbor Finding Techniques for Imagees Represented Quadtrees. Academic Press 18: 35-57.

8. Samet H. and M. Tamminen.(1985) IEEE Transaction on Patter Analysis and Machine Intelligence. Computing Geometric Properties of Images Represented by Linear Quadtrees. March: 229-240.

9. Burroughs,P.A. (1986) Principles of Geographical Information Systems for Land Resources Assessment. Clarendon Press: Oxford.

10. Foley J.D. and A. Van Dam(1982) Fundamentals of Interactive Computer Graphics. Addison Wesley.

11. Carlbom I., I. Chakravarty and D. Vanderschel (1985) A Hierarchical Data Structure for Representing the Spatial Decomposition of 3D Objects. In: Frontiers in Computer Graphics (T.L. Kunii ed.), pp. 2-12. Springer-Verlag: New York.

12. Burger, P. and D. Gillies (1989) Interactive Computer Graphics: Functional, Procedural and Device-level Methods. Addison-Wesley Publishing Company: Sydney.

Ссылки на интернет ресурсы

13. http://loi.sscc.ru/gis/QUADTREE/QUADTREE.html

14. http://www.kolasc.net.ru/cdo/metod/programmer"scourse/language/oop_pas.htm

15. https://ru.wikipedia.org/wiki/Заглавная_страница

Размещено на