Результаты.

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. Кошкарев А.В., Тикунов В.С.

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.