Задача обхода плоскости возникает при обработке двумерных данных. Цель: создание одномерного массива D из двумерного массива S. Причем если предполагается последующее сжатие D, то желательно создавать его так, чтобы "разрывов" было как можно меньше: каждый следующий эле­мент Д, заносимый в D на i-m шаге, является соседним (в плоскости) для предыдущего, занесенного в D на (/-1)-м шаге, Д./.

Змейка (зигзаг-сканирование)

Обход массива S начинается с одного угла плоскости, заканчивается в противоположном по диагонали. Например, из левого верхнего в правый нижний:

1	2	6	7	15	16
3	5	8	14	17	24
4	9	13	18	23	25
10	12	19	22	26	29
11	20	21	27	28	30

На иллюстрации показан порядок выборки элементов из плоскости (с последующим занесением в одномерный массив). Значение из ячейки массива S, помеченной на рисунке номером i, заносится в D[i].

Змейка выгодна в случаях, когда в одном из углов "особенность", на­пример сосредоточены самые крупные коэффициенты. Применяется в алго­ритме JPEG для обхода квадрантов (размером 8x8 точек).

Обход строками

Самый тривиальный метод. Именно он используется в самых распро­страненных графических форматах (BMP, TGA, RAS...) для хранения эле­ментов изображений.

1	2	3	4	5	6
7	8	9	10	11	12
13	14	15	16	17	18
19	20	21	22	23	24
25	26	27	28	29	30
разв	оротг	1МИ Л	уы кг	1ЖД01	[ BTOI

борку в обратном направлении:

1	2	3	4	5	6
12	11	10	9	8	7
13	14	15	16	17	18
24	23	22	21	20	19
25	26	27	28	29	30

Точек "разрыва" нет, в отличие от варианта без разворотов. Совершенно аналогично можно делать обход столбцами.

Упражнение. Нарисуйте пример обхода плоскости столбцами с разворотами.

Обход полосами

Чаще всего сжатие лучше, если каждая область двумерного массива S не рассредоточена (равномерно "размазана") по всему одномерному D, а скон­центрирована в D компактно. В случае обхода строками понятие "области" отсутствует: каждый элемент считается "областью". Пытаясь обходить плоскость квадратами размером NxN, приходим к идее обхода горизонталь­ными "полосами" шириной N:

1	4	7	10	13
2	5	8	11	14
3	6	9	12	15
16	19	22	25	28
17	20	23	26	29
18	21	24	27	30

В данном примере ширина полосы N=3. Если N=1, получаем обход строками.

Полосами с разворотами

То же самое, но с разворотами и столбцов внутри полос, и направлений самих полос:

1	6	7	12	13
2	5	8	11	14
3	4	9	10	15
28	27	22	21	16
29	26	23	20	17
30	25	24	19	18

Разрывов опять нет, но теперь еще и каждая точка принадлежит к облас­ти, записанной в D компактно, без разрывов: ее элементы расположены внутри одного интервала (£>[/], /)[i+l], ■••, D[i+f\) и элементов из других об­ластей внутри этого интервала нет. Примеры таких областей - каждый из четырех углов размером 3x3 элемента.

Упражнение. Нарисуйте схему обхода квадрата 7x7 полосами шириной 3 с разворотами. Какой вариант лучше: 3+3+1 или 3+2+2? Какие области заносят­ся в D компактно?

Обход решетками

Для первой порции берем элементы из каждого N-ro столбца каждой М-й строки. Для второй - то же, но со сдвигом на один столбец. Так же и для следующих, а затем - со сдвигом на одну, две, (М-1) строки. Например, если M=N=2, то имеем 4 порции:

1	13	2	14	3	15	4	16
25	37	26	38	27	39	28	40
5	17	6	18	7	19	8	20
29	41	30	42	31	43	32	44
9	21	10	22	11	23	12	24
33	45	34	46	35	47	36	48

То есть плоскость разбивается на прямоугольники размера MxN, задается обход плоскости прямоугольниками, а также обход внутри самих прямо­угольников и далее делается "одновременный" обход по каждому из них: сначала выбираются их первые элементы, затем вторые, третьи, и т. д., до последнего.

Обход решетками с учетом значений элементов

После того как обработаны первые элементы прямоугольников (в нашем примере - квадратов 2x2), если предположить, что они являются атрибутан ми своих областей, выгодно (для улучшения сжатия) группировать области с одинаковыми атрибутами, т. е. с одинаковыми значениями этих первых элементов.

Допустим, атрибуты распределены так:

R		G		G		G
L		R		G		G
L		L		R		R

Тогда имеет смысл дальше действовать так:

R	13	G	25	G	28	G	31
15	14	27	26	30	29	33	32
L	40	R	16	G	34	G	37
42	41	18	17	36	35	39	38
L	43	L	46	R	19	R	22
45	44	48	47	21	20	24	23

То есть сначала обходим квадраты с атрибутом "R", затем с атрибутом "G" и, наконец, с "L".

Контурный обход

Часть элементов принадлежит к одной группе, часть - к другой, причем контур задан:

	1	1	1	1	1
	1	21	2:	1	1
	2	21	М	2|	1
	121	т	Я	т	й
	1	1	ш	1	1
	1	1	1	1	1

36 элементов - из группы "1", а 12 - из группы "2".

Очевидно, что имеет смысл отдельно оформить элементы группы "1"

1	29	28	27	26	22	21	31
2	30			25	23	20	32
3					24	19	33
4						18	34
5	8	9		13	14	17	35
6	7	10	И	12	15	16	36

и затем точно так же остальные элементы, принадлежащие к группе "2"

Контурный обход с неизвестными контурами

Рассмотрим предыдущий пример, т. е. такое же распределение элемен­тов групп по плоскости, но изначально, при начале обхода плоскости, это распределение неизвестно. Будем действовать таким методом:

1	44	41	40	35	34	29	28
2	43	42::.	39	36	33	30	27
3	45	46^	38	37 .-	32	31	26
4	9Й	ю :	47"	48	19;.	20	25
5	8	п	14	15	18	21	24
6	7	12	13	16	17	22	23

Обходим плоскость "столбцами с разворотами" и, обнаруживая элемент

другой группы (в элементах 9, 10, 14...), также делаем разворот на 180°. За­тем (шаги 45-48) обходим оставшуюся часть плоскости, содержащую (предположительно) элементы другой группы. В итоге имеем:

■ среди первых 36 элементов 4 из группы "2", а 32 из группы "1";

■ из последних 12 элементов 8 из группы "2", а 4 из группы" 1".

В первой части 4/36=1/9 "исключений", во второй - 4/12=1/3. А если бы делали просто обход "столбцами с разворотами":

1	12	13	24	25	36	37	48
2	11	.1*44	23г«	26	35	38	47
3	10-*.	15Ш	2*»	27JK	34	39	46
4	9 :&i	16-	21;;?	28»	ззе	40	45
5	8	17	20*	29	32	41	44
6	7	18	19	30	31	42	43

В итоге:

■ среди первых 33 элементов 12 из группы "2", а 21 из группы "1";

■ из последних 15 элементов все из группы" 1".

То есть в большей части получившегося блока - более чем 1/3 "исключений".

"Квадратная змейка"

Рекурсивный метод для квадратных областей.

Если принять левый верхний элемент за первый, то для квадрата 2x2 возможны два варианта обхода без разрывов:

1	4
2	3

1	2
4	3

То есть либо первый переход внутри квадрата был сверху вниз, тогда пя­тым шагом будет переход к левому верхнему элементу квадрата справа

(или к правому нижнему элементу квадрата сверху). Либо, наоборот, пер­вый переход внутри квадрата был вправо, тогда пятым шагом будет пере­ход к квадрату снизу (или слева). Переформулируем так:

■ если нужно выйти к правому (или верхнему) квадрату, то первый шаг -вниз, если к нижнему (или левому), то первый шаг - вправо;

■ пройденным путем однозначно задается, к какому квадрату нужно вый­ти в каждый конкретный момент;

■ только в самом начале есть выбор одного из двух вариантов обхода. Например:

Первый шаг внутри квадрата 2x2 был вправо, - значит, в результате об­хода этого квадрата 2x2 мы должны выйти к нижнему квадрату 2x2.

Первый шаг перехода от 2x2 к 2x2 внутри 4x4 был вниз, - значит, мы должны выйти к правому 4x4.

Первый переход внутри квадрата 16x16 был вправо, - значит, в резуль­тате обхода 16x16 мы должны прийти к нижнему, и т. д.

Разрывов нет, и каждый элемент принадлежит к области, записанной компактно.

ЭД. Упражнение. Определите, какие числа должны быть в незаполненных клетках примера. Нарисуйте другой пример: при выборе второго элемента квадрата делаем переход не слева направо, а сверху вниз.

Для квадрата 3x3 можно взять такие два "шаблона":

1	4	5
2	3	6
9	8	7

1	2	9
4	3	8
5	6	7

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

■ если нужно выйти к правому (или верхнему) квадрату, то первый шаг - вправо, если к нижнему (или левому), то первый шаг - вниз;

■ пройденным путем однозначно задается, к какому квадрату нужно вый­ти в каждый конкретный момент;

■ только в самом начале есть выбор одного из двух вариантов.

Но для 3x3 есть еще и такие варианты:

1	6	7
2	5	8
3	4	9

1	2	3
6	5	4
7	8	9

Видно, что они совершенно эквивалентны, т. е. взаимозаменяемы, по­скольку в обоих случаях мы выходим в правый нижний угол. Точно так же эквивалентны и два варианта обхода ими квадрата 9x9:

1					18	19
		9	10					27
		46	45					28
54					37	36
55					72	73
		63	64					81

И

1					54	55
		9	46					63
		10	45					64
18					37	72
19					36	73
		27	28					81

Совершенно аналогично для 5x5, и затем 25x25 и т. д.

Если требуется обойти квадрат размера NxN, сначала определяем, про­изведением каких простых чисел является N, затем задаем порядок этих чи­сел в произведении (а для каждого нечетного множителя еще и направление обхода). Таким образом будет задан процесс обхода.

Если К, равное числу двоек в произведении, больше одного: К>1, то сторона самого мелкого квадрата должна быть 2^К"' или 2^К элементов. На­пример, если К.=3, то обход без разрывов 2x3x2x2 (от самого мелкого 2x2 к 6x6, затем к 12x12 и, наконец, к 24x24) невозможен:

		63	64					9	10
	59			68			5			14
55					72	1					18
54					37	36					19
	50			41			32			23
		46	45					28	27
						73

Каждая ячейка этой таблицы - квадрат 2x2; нижние 5 строк пропущены: перейти к двум нижним квадратам 12x12 без разрыва не сможем.

Других ограничений при обходе "квадратной змейкой" нет.

Каждый квадрат со стороной L>2 можно обходить обычной змейкой, а не "квадратной". Это выгодно в том случае, если наиболее различаю­щиеся элементы сгруппированы в противоположных углах квадрата.

S*. Упражнение. Нарисуйте порядок обхода квадрата 25x25, а затем - квадрата 12x12. Убедитесь, что разрывов нет и каждый элемент принадлежит к компакт­но записанной области.

Обход по спирали

Обход по спирали довольно тривиален. Строится квадрат 3x3, затем 5x5, затем 7x7,9x9 и т. д.:

43	44	45	46	47	48	49
42	21	22	23	24	25	26
41	20	7	8	9	10	27
40	19	6	1	2	11	28
39	18	5	4	3	12	29
38	17	16	15	14	13	30
37	36	35	34	33	32	31

Если же строить круги радиуса 2, 3,4 и т. д., неизбежно будут присутст­вовать точки разрыва. Спираль может быть и сходящейся. Суть ее можно показать с помощью этой же иллюстрации, только направление движения обратное: от 49 к 1. Кроме того, она может быть с разворотами:

1	2	3	4	5	6	7
24	25	40	39	38	37	8
23	26	41	42	43	36	9
22	27	48	49	44	35	10
21	28	47	46	45	34	11
20	29	30	31	32	33	12
19	18	17	16	15	14	13

Направление изменяется в точках, расположенных на диагонали: в дан­ном примере это "25" и "41".

Общие моменты для прямоугольных методов

В любом случае можно начать с одного из четырех углов и дальше дви­гаться в одном из двух направлений: по вертикали и по горизонтали. Пер­вое, т. е. положение первого угла, влияния на степень сжатия почти не ока­зывает, особенно при сжатии изображений. А вот второе, выбор направле­ния, может существенно улучшить сжатие, поскольку области в этих двух случаях (основное направление по вертикали или по горизонтали) будут сгруппированы по-разному.

Например, отсканированный текст лучше сжимать, обходя по вертикали, поскольку в нем больше длинных сплошных вертикальных линий, чем го­ризонтальных.

Общие моменты для методов сложной формы

Возьмем на обслуживание компьютеры организаций, компьютерная помощь.

Может возникнуть необходимость помечать уже обработанные точки плоскости, чтобы избежать лишних вычислений, предотвращающих по­вторное их занесение в D. Тогда есть два основных варианта: либо добавить по одному "флаговому" биту для каждой точки плоскости, либо выбрать (или добавить) значение для "флага", показывающего, что точка уже внесе­на в D, и записывать это значение на место уже внесенных точек.