Алгоритмы закраски фигур

@slavek777 · Регистрация: 15.09.2016

Author24 — интернет-сервис помощи студентам

Здравствуйте, есть задание (opengl древний):
Написать необходимые функции С++ для реализации РАСТРОВЫХ алгоритмов:
− ЗАКРАСКА окружности;
− закраска эллипса;
− закраска многоугольника;
− закраска произвольной области.

И не дается никаких ссылок, пояснений. Читаю в интернете про простые алгоритмы растрирования отрезков(линий). Но не понимаю, причем тут это к фигурам. И наталкиваюсь на классификацию алгоритмов, что совсем меня диозориентирует.

Мне нужно написать алгоритм определения, например, все той же окружности/эллипса. Меня смущает слово - закраска. Я делал ее просто так раньше - брал, рисовал по формуле (или задавал вручную) при помощи примитивов gl_triangle или gl_quad, а перед этим прописывал цвет параметрически при помощи gl_color. И как понять сущность многоугольника, при неизвестном количестве сторон (просто буквенную переменную? хорошо, допустим.. но что делать с произвольной областью - делать через ограничивающие линии?)

@8Observer8 · 07.02.2020, 16:55

Сообщение от slavek777

но что делать с произвольной областью - делать через ограничивающие линии?

Использовать алгоритм Заливка

Название: Recursive_Flood_Fill_4_%28aka%29.gif
Просмотров: 162

Размер: 2.3 Кб

@Excalibur921 · 07.02.2020, 17:34

Сообщение от slavek777

Написать необходимые функции С++ для реализации РАСТРОВЫХ алгоритмов:

Какой суровый шаг назад. Зачем такие задания…

Сообщение от slavek777

есть задание (opengl древний):

Причем тут тогда opengl?

Сообщение от slavek777

закраска произвольной области.

Тут могут быть самопересечения по идее…а значит алгоритм “Заливка” не будет работать. Может
Реализовать типа спрея из Paint? Ведь не указано что произвольная область задается ломанной.

Сообщение от slavek777

наталкиваюсь на классификацию алгоритмов

Странный подход, если велосипеды делать то скорей искать книги типа “компьютерная графика на ЭВМ”

@slavek777 · 07.02.2020, 17:36 **[ТС]**

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

"Этот алгоритм является слишком неэффективным, так как для всякого
уже отрисованного пикселя функция вызывается ещё 4 раза и, кроме того,
данный алгоритм не пригоден для закрашивания контуров фигур площадью в
тысячу и более пикселей, так как вложенные вызовы функций делаются для
каждого пикселя, что приводит к переполнению стека в ходе выполнения
программы.Поэтому для решения задачи закраски области предпочтительнее алго-
ритмы, способные обрабатывать сразу целые группы пикселей, т. е. исполь-
зовать их «связность». Если данный пиксель принадлежит области, то, скорее
всего, его ближайшие соседи также принадлежат данной области. Группой
таких пикселей обычно выступает полоса, определяемая правым пикселем.
Алгоритм закрашивания линиями. Данный алгоритм получил широкое
распространение в компьютерной графике. От простейшего алгоритма он от-
личается тем, что на каждом шаге закрашивания рисуется горизонтальная
линия, которая размещается между пикселями контура." И все... больше никакой информации.

А метод приложу.

C++

        public static void BresenhamCircle(Graphics g, Color clr, int _x, int _y, int radius)
        {
            int x = 0, y = radius, gap = 0, delta = (2 - 2 * radius);
            while (y >= 0)
            {
                PutPixel(g, clr, _x + x, _y + y, 255);
                PutPixel(g, clr, _x + x, _y - y, 255);
                PutPixel(g, clr, _x - x, _y - y, 255);
                PutPixel(g, clr, _x - x, _y + y, 255);
                gap = 2 * (delta + y) - 1;
                if (delta < 0 && gap <= 0)
                {
                    x++;
                    delta += 2 * x + 1;
                    continue;
                }
                if (delta > 0 && gap > 0)
                {
                    y--;
                    delta -= 2 * y + 1;
                    continue;
                }
                x++;
                delta += 2 * (x - y);
                y--;
            }
        }

@snake32 · 07.02.2020, 18:09

Хабре есть неплохая софтовая реализация OpenGL (может чем-то поможет)
https://habr.com/ru/post/248153/
Но там закраска только линии и треугольника. Впрочем любой полигон можно триангулировать - представить в виде треугольников

@Excalibur921 · 07.02.2020, 21:31

Сообщение от snake32

Но там закраска только линии и треугольника.

Я бы пилил алгоритм треугольников. Все эти задачи можно разбить на “закрась треугольник”.

“Клетка геометрии – треугольник. Он так же неисчерпаем, как и вселенная. Игорь Фёдорович Шарыгин”

Странное совпадение.

@slavek777 5 / 5 / 1 Регистрация: 15.09.2016 Сообщений: 410
		1
	Алгоритмы закраски фигур 07.02.2020, 16:28. Показов 4818. Ответов 5 Метки нет (Все метки) Здравствуйте, есть задание (opengl древний): Написать необходимые функции С++ для реализации РАСТРОВЫХ алгоритмов: − ЗАКРАСКА окружности; − закраска эллипса; − закраска многоугольника; − закраска произвольной области. И не дается никаких ссылок, пояснений. Читаю в интернете про простые алгоритмы растрирования отрезков(линий). Но не понимаю, причем тут это к фигурам. И наталкиваюсь на классификацию алгоритмов, что совсем меня диозориентирует. Мне нужно написать алгоритм определения, например, все той же окружности/эллипса. Меня смущает слово - закраска. Я делал ее просто так раньше - брал, рисовал по формуле (или задавал вручную) при помощи примитивов gl_triangle или gl_quad, а перед этим прописывал цвет параметрически при помощи gl_color. И как понять сущность многоугольника, при неизвестном количестве сторон (просто буквенную переменную? хорошо, допустим.. но что делать с произвольной областью - делать через ограничивающие линии?) Миниатюры 0

@8Observer8 5158 / 2770 / 465 Регистрация: 05.10.2013 Сообщений: 7,321 Записей в блоге: 147
	07.02.2020, 16:55	2
	Сообщение от slavek777 но что делать с произвольной областью - делать через ограничивающие линии? Использовать алгоритм Заливка 0

@Excalibur921 1471 / 826 / 140 Регистрация: 12.10.2013 Сообщений: 5,456
	07.02.2020, 17:34	3
	Сообщение от slavek777 Написать необходимые функции С++ для реализации РАСТРОВЫХ алгоритмов: Какой суровый шаг назад. Зачем такие задания… Сообщение от slavek777 есть задание (opengl древний): Причем тут тогда opengl? Сообщение от slavek777 закраска произвольной области. Тут могут быть самопересечения по идее…а значит алгоритм “Заливка” не будет работать. Может Реализовать типа спрея из Paint? Ведь не указано что произвольная область задается ломанной. Сообщение от slavek777 наталкиваюсь на классификацию алгоритмов Странный подход, если велосипеды делать то скорей искать книги типа “компьютерная графика на ЭВМ” 0

@snake32 3420 / 1607 / 236 Регистрация: 26.02.2009 Сообщений: 7,856 Записей в блоге: 5
	07.02.2020, 18:09	5
	Хабре есть неплохая софтовая реализация OpenGL (может чем-то поможет) https://habr.com/ru/post/248153/ Но там закраска только линии и треугольника. Впрочем любой полигон можно триангулировать - представить в виде треугольников 0

@Excalibur921 1471 / 826 / 140 Регистрация: 12.10.2013 Сообщений: 5,456
	07.02.2020, 21:31	6
	Сообщение от snake32 Но там закраска только линии и треугольника. Я бы пилил алгоритм треугольников. Все эти задачи можно разбить на “закрась треугольник”. “Клетка геометрии – треугольник. Он так же неисчерпаем, как и вселенная. Игорь Фёдорович Шарыгин” Странное совпадение. 1