0.4.2 Сортировка методом распределяющего подсчета

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

Для рассмотрения алгоритма предположим, что надо отсортировать числа, заданные в массиве с именем "Исходный_массив"; количество сортируемых чисел задается скаляром "Кол-во_чисел"; сортируемые числа J удовлетворяют условию:

0 Ј J < Max_число.

Для сортировки потребуются описания:

int Max_число; /* Верхняя граница значений */

int *Повтор; /* Длина этого массива = Max_число */

int Кол_чисел; /* Кол-во сортируемых чисел */

int *Исходный_массив; /* Длина этого массива >= Кол_чисел */

int *Результат; /* Длина этого массива >= Кол_чисел */

int ii,jj, kk; /* Рабочие переменные */

1. Обнуляется служебный массив для подсчета числа повторений исходных кодов.

2. for (ii=0; ii<Max_число; ++ii) Повтор[ii]= 0;

3. Сортируемый массив просматривается и вычисляется количество раз повторений каждого числа:

4. for (ii= 0; ii < Кол_чисел; ++ii) {

5. jj= Исходный_массив[ii];

6. Повтор[jj]= Повтор[jj] + 1;

7. }

8. Суммируется количество повторений каждого числа, так что значение Повтор[J] даст начальное расположение группы чисел, равных J, в отсортированном массиве:

9. jj= 0;

10. for (ii=0; ii<Max_число; ++ii) {

11. jj= jj + Повтор[ii];

12. Повтор[ii]= jj;

13. }

14. Просматривается исходный массив и числа из него заносятся в массив результатов той же длины. Индекс занесения числа J в массив результатов равен значению J-го элемента массива Повтор. После занесения числа J значение Повтор[J] уменьшается на 1:

15. for (ii= 0; ii < Кол_чисел; ++ii) {

16. jj= Исходный_массив[ii];

17. kk= Повтор[jj];

18. Результат[kk]= jj;

19. Повтор[jj]= Повтор[jj] - 1;

20. }

0.5 Заливка области с затравкой

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

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

По способу задания области делятся на два типа:

· гранично-определенные, задаваемые своей (замкнутой) границей такой, что коды пикселов границы отличны от кодов внутренней, перекрашиваемой части области. На коды пикселы внутренней части области налагаются два условия - они должны быть отличны от кода пикселов границы и кода пиксела перекраски. Если внутри гранично-определенной области имеется еще одна граница, нарисованная пикселами с тем же кодом, что и внешняя граница, то соответствующая часть области не должна перекрашиваться;

· внутренне-определенные, нарисованные одним определенным кодом пиксела. При заливке этот код заменяется на новый код закраски.

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

Заливаемая область или ее граница - некоторое связное множество пикселов. По способам доступа к соседним пикселам области делятся на 4-х и 8-ми связные. В 4-х связных областях доступ к соседним пикселам осуществляется по четырем направлениям - горизонтально влево и вправо и в вертикально вверх и вниз. В 8-ми связных областях к этим направлениям добавляются еще 4 диагональных. Используя связность мы может, двигаясь от точки затравки, достичь и закрасить все пикселы области.

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

В общем, 4-х связную область мы можем заполнить как 4-х, так и 8-ми связным алгоритмом. Обратное же неверно. Так область на рис. а мы можем заполнить любым алгоритмом, а область на рис. б, состоящую из двух примыкающих 4-х связных областей можно заполнить только 8-ми связным алгоритмом.

Рис. 0.5.1: Связность областей и их границ

С использованием связности областей и стека можно построить простые алгоритмы закраски как внутренне, так и гранично-определенной области. В [] рассматриваются совсем короткие рекурсивные подпрограммы заливки. В [] - несколько более длинные итеративные подпрограммы.