Результаты.

program Project1;

uses Crt;

const

XMAX = 6;

YMAX = 6;

type

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

PQTree = ^TQTree;

TQTree = object

Name: string;

NW, NE, SW, SE: PQTree;

constructor Create(TreeName: string);

procedure ScanMatrix(M: TMatrix; X1, Y1, X2, Y2: Integer);

procedure View(Pad: Integer);

destructor Destroy;

end;

var

M1, M2: TMatrix;

T1, T2: PQTree;

procedure FillMatrix(var M: TMatrix);

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(M: TMatrix);

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;

constructor TQTree.Create(TreeName: string);

begin

Self.Name := TreeName;

Self.NW := nil;

Self.NE := nil;

Self.SW := nil;

Self.SE := nil;

end;

procedure TQTree.ScanMatrix(M: TMatrix; X1, Y1, X2, Y2: Integer);

var

x, y: Integer;

Finded1, Finded2: Boolean;

dx, dy: Integer;

TmpX1, TmpY1, TmpX2, TmpY2: Integer;

begin

Finded1 := False;

Finded2 := False;

for x := X1 to X2 do

for y := Y1 to Y2 do

begin

if M[x, y] = 0 then

Finded1 := True;

if M[x, y] = 1 then

Finded2 := True;

if Finded1 and Finded2 then

begin

dx := (X2 - X1) div 2;

dy := (Y2 - Y1) div 2;

{NW}

TmpX1 := X1;

TmpX2 := X1 + dx;

TmpY1 := Y1;

TmpY2 := Y1 + dy;

Self.NW := New(PQTree, Create('NW'));

Self.NW^.ScanMatrix(M, TmpX1, TmpY1, TmpX2, TmpY2);

{NE}

TmpX1 := X1 + dx + 1;

TmpX2 := X2;

TmpY1 := Y1;

TmpY2 := Y1 + dy;

Self.NE := New(PQTree, Create('NE'));

Self.NE^.ScanMatrix(M, TmpX1, TmpY1, TmpX2, TmpY2);

{SW}

TmpX1 := X1;

TmpX2 := X1 + dx;

TmpY1 := Y1 + dy + 1;

TmpY2 := Y2;

Self.SW := New(PQTree, Create('SW'));

Self.SW^.ScanMatrix(M, TmpX1, TmpY1, TmpX2, TmpY2);

{SE}

TmpX1 := X1 + dx + 1;

TmpX2 := X2;

TmpY1 := Y1 + dy + 1;

TmpY2 := Y2;

Self.SE := New(PQTree, Create('SE'));

Self.SE^.ScanMatrix(M, TmpX1, TmpY1, TmpX2, TmpY2);

Break;

end;

end;

end;

procedure TQTree.View(Pad: Integer);

var

i: Integer;

begin

if @Self <> nil then

begin

Self.NE^.View(Pad + 3);

Self.NW^.View(Pad + 3);

for i := 1 to Pad do

Write('-');

WriteLn(Self.Name);

Self.SW^.View(Pad + 3);

Self.SE^.View(Pad + 3);

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(M1);

Writeln('Matrix 1: ');

WriteMatrix(M1);

FillMatrix(M2);

Writeln('Matrix 2: ');

WriteMatrix(M2);

T1 := New(PQTree, Create('Tree1'));

T2 := New(PQTree, Create('Tree2'));

T1^.ScanMatrix(M1, 1, 1, XMAX, YMAX);

T2^.ScanMatrix(M2, 1, 1, XMAX, YMAX);

ReadLn;

T1^.View(1);

Writeln;

ReadLn;

T2^.View(1);

ReadLn;

Dispose(T1, Destroy);

Dispose(T2, Destroy);

end.

Вывод.

Использование квадродерева продемонстрировано на классической задаче разбора бинарной матрицы N на M. Для примера в программе используется матрица 8 на 8, которая заполняется случайным образом. Сначала выводится матрица, потом выводятся данные по ходу формирования дерева, затем выводится само дерево.

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

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

Пометки обозначают:

Root - корень,

NW - северо-запад,
NE - северо-восток,

SW - юго-запад,
SE - юго-восток. TQTree – класс

M1, M2: Tmatrix, T1, T2: PQTree – процедуры с помощью которых в классе создаются матрицы

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

Рис. 5: Матрица 1,2

Рис. 6: Визуализация квадродерева по 1 матрице

Рис. 7: Визуализация квадродерева по 2 матрице

Литература

1. Кошкарев А.В., Тикунов В.С.

a. Геоинформатика. Москва, Картгеоцентр-Геоиздат, 1993. С. 55-57.

2. Tobler, W., Zi-tan Chen. (1986)

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

3. Mark D.M. (1986)

a. 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)

a. 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)

a. IEEE Transactions on Pattern Analysis and Machine Intelligence. Operations on Images Using Quad Trees. April: 145-153.

6. Samet,H. (1990)

a. The Design and Analysis of Spatial Data Structures. Addison-Wesley Publishing Company, Inc : Reading.

7. Samet H.(1981)

a. Computer Graphics and Image processing. Neighbor Finding Techniques for Imagees Represented Quadtrees. Academic Press 18: 35-57.

8. Samet H. and M. Tamminen.(1985)

a. 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)

a. Principles of Geographical Information Systems for Land Resources Assessment.
Clarendon Press : Oxford.

10. Foley J.D. and A. Van Dam(1982)

a. Fundamentals of Interactive Computer Graphics. Addison Wesley.

11. Carlbom I., I. Chakravarty and D. Vanderschel (1985)

a. 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)

a. Interactive Computer Graphics: Functional, Procedural and Device-level Methods. Addison-Wesley Publishing Company: Sydney.