Практика 03. Закрашивание фигур

Практика 03. Закрашивание фигур

Фигура – это объект, состоящий из контура (контуров) и ограниченной данным контуром области. Контур – это линия, например, отрезок прямой, дуга окружности или просто несколько последовательных пикселов – всё это вы уже умеете выводить.

Цель данной практической работы – научиться выводить внутреннюю область фигур, иными словами – закрашивание.

Задача 0. Подготовка

Для начала создайте битовую карту, с контуром (набором линий), ограничивающим небольшую область, например, так:

Для примера, попробуем закрасить квадрат в центре.

Задача 1. Закрашивание точками

Наверняка, каждый работал с программой Paint. Закрашивание там производилось следующим образом: рисовался контур, затем выбиралась точка внутри него (точка, на которую пользователь щёлкал банкой с краской), и от неё производилась заливка. Мы поступим таким же образом.

Реализуйте методPointFill(). Параметры придумайте сами.

Алгоритм вам известен:

1. Закрашивается сама точка (x, y) в цвет заполнения

2. Если цвет точки (x+1, y) совпадает с цветом фона, то рекурсивно вызываем функцию для точки (x+1, y)

3. То же самое для точек (x-1, y),(x, y+1)и (x, y-1)

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

bm.GetPixel(x, y);

Метод вернёт объект класса Color, который можно сравнивать с другими подобными объектами.

В результате, ваш объект должен быть заполнен:

P.S. Подумайте, откуда взять цвет фона для первого (нерекурсивного) вызова метода.

P.P.S. Где-то в методе надо пристроить проверку на выход за границы битовой карты, т. к. в общем случае пользователь может указать в качестве отправной точку, не лежащую внутри контура, и тогда нужно будет залить всю карту.

Впрочем, в данный момент всю битовую карту закрасить у вас не получится – не хватит стека рекурсивных вызовов. В этом и заключается основной недостаток данного метода – он работает только с объектами небольших размеров. Стоит указать размер побольше – закончится стеквызовов. Поэтому, метод необходимо оптимизировать.

Задача 2. Закрашивание линиями

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

Реализуйте метод LineFill().

Алгоритм закрашивания линиями следующий:

1. Получаем отправную точку и определяем цвет фона;

2. От отправной точки шагаем влево до тех пор, пока цвет пикселя равен цвету фона, или до границы карты (ищем контур) – точка A;

3. От отправной точки шагаем вправо до тех пор, пока цвет пикселя равен цвету фона, или до границы карты (ищем контур) – точка B;

4. Выводим отрезок ABнужного цвета;

5. От Aдо Bдля каждой точки (x, y) проверяем:

a. Если точка (x, y+1)имеет цвет фона, то рекурсивно вызываем функцию ЗАКРАШИВАНИЕ для неё в качестве отправной;

b. Если точка (x, y-1)имеет цвет фона, то рекурсивно вызываем функцию ЗАКРАШИВАНИЕ для неё в качестве отправной;

С помощью этого метода закрасьте большой объект.

Или, если вы уже сделали домашнюю работу:

Стековой памяти должно хватить.

От рекурсии вообще можно отказаться, используя другой алгоритм закрашивания.

Задача 3. Волновой алгоритм закрашивания

Название данному алгоритму дано из-за того, что он имитирует расходящиеся волны от брошенного в воду камешка (или постепенное размытие капли краски).

Реализуйте метод WaveFill().

Для реализации алгоритма нам понадобится дополнительный список, в котором будут храниться вершины, соседей которых мы ещё не закрасили. Это аналог списка openedиз задачи обхода дерева. В терминах данного алгоритма он называется фронт волны (wavefront).

Алгоритм:

1. Записать во фронт волны начальную точку.

2. Выполнять до тех пор, пока фронт не будет пуст:

a. Закрасить первый элемент фронта

b. Добавить во фронт соседей, цвет которых равен фону и которых ещё нет во фронте(это важно во избежание зацикливания)

c. Удалить первый элемент из фронта

P.S. В этой задаче вам придётся поработать со списками.

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

Appendix. Списки

Работа со списками в C# так или иначе связана с манипуляциями с классом List.Listэто обобщённый тип (это означает, что с разными параметрами он работает по разному), поэтому необходимо указывать, список чего вы хотите создать. В C++ подобное поведение известно под названием «шаблоны».

Иными словами, список целых чисел можно создать так:

List<int> a = new List<int>();

Точно также, как и создание обычного объекта класса. А вот так будет выглядеть создание списка точек (представителей класса Point):

List<Point> a = new List<Point>();

Список – динамическая структура данных, это означает, что его элементы добавляются и удаляются в процессе его жизни (собственно, для этого он и придуман).

Добавление элемента в список выполняется при помощи метода Add, параметром которого является объект, который требуется добавить. Например так:

a.Add(p);

Здесь a – это список точек, p–какая-то точка.

Аналогично совершается удаление из списка. Для этого есть метод Remove, который удаляет данный объект из списка:

a.Remove(p);

К элементам списка можно обращаться точно так же, как к элементам массива:

a[0]; a[i]; a[i++] и т. д.

Кроме того, в процессе работы алгоритма нужно будет проверять, не пуст ли данный список. Легче всего это сделать при помощи свойства Count, которое возвращает количество элементов в списке:

a.Count;

Очевидно, что если количество элементов равно нулю, то список пуст.

Так же, по задаче вам придётся проверять, входит ли данный элемент в список. Для этого применяется метод Contains. Параметр – элемент, существование которого нужно проверить. Метод возвращает trueили false.

a.Contains(p);

С помощью указанных методов вы вполне можете решить данную задачу.

На этом данная лабораторная работа завершена. Не думайте, что я забыл про алгоритм XY, им вы насладитесь в следующем семестре.