Алгоритм вывода окружности
Для вывода контура окружности можно использовать соотношение между координатами X и Y для точек окружности X2 + Y2 = R2и построить алгоритм прямого вычисления координат. Однако тогда необходимо вычислять квадратный корень, а это в цифровом компьютере выполняется медленно. Дадим запись инкрементного алгоритма Брезенхейма языком C++: void Circle(int xc, int ус, int radius) { int x, у, dxt; long r2, dst, t, s, e, ca, cd, indx; r2 = (long)radius*(long)radius; dst = 4*r2; dxt = (double)radius/1.414213562373; t = 0; s = -4*r2*(long)radius; e = (-s/2) - 3*r2; ca = -6*r2; cd = -10*r2; x = 0; у = radius; //Пиксел (xc, yc+radius); //Пиксел (xc, ус-radius); //Пиксел (xc+radius, yc); //Пиксел (xc-radius, yc); for (indx = 1; indx <= dxt; indx++) { x++; if (e >= 0) e += t + ca; else { y--; е += t - s + cd; s += dst; } t -= dst; //Пиксел (xc+x, yc+y); //Пиксел (xc+y, yc+x); //Пиксел (xc+y, yc-x); //Пиксел (xc+x, yc-y); //Пиксел (xc-x, yc-y); //Пиксел (xc-y, yc-x); //Пиксел (xc-y, yc+x); //Пиксел (xc-x, yc+y); } } В этом алгоритме использована симметрия окружности — в основном цикле вычисляются координаты точек окружности только для одного октанта и сразу рисуются восемь симметрично расположенных пикселов. Кривая Безье Разработана математиком Пьером Безье. Кривые и поверхности Безье были использованы в 60-х годах компанией "Рено" для компьютерного проектирования формы кузовов автомобилей. В настоящее время они широко используются в компьютерной графике. Кривые Безье описываются в параметрической форме: х = Px(t), у = Py(t). Значение tвыступает как параметр, которому соответствуют координаты отдельной точки линии. Параметрическая форма описания может быть удобнее для некоторых кривых, чем задание в виде функции у=f(x),поскольку функция f(x)может быть намного сложнее, чем Px(t) и Py(t), кроме того,f(х) может быть неоднозначной. Многочлены Безье для Рх и Рy имеют такой вид: где хiи уi - координаты точек-ориентиров Рi, а величины - это известные из комбинаторики, так называемые сочетания (они также известны как коэффициенты бинома Ньютона): Значение т можно рассматривать и как степень полинома, и как значение, которое на I единицу меньше количества точек-ориентиров. Рассмотрим кривые Безье, классифицируя их по значениям т. т = 1 (по двум точкам) Кривая вырождается в отрезок прямой линии, которая определяется конечными точками Р0 и Р1, как показано на рис. 72: P(t) = (1- t)P0 + t1 т=2 (по трем точкам, рис. 73): P(t) = (1- t)2P0 + 2t(1- t)P1 + t2P2.
Рис. 72 Рис. 73 m - 3 (по четырем точкам, кубическая, рис 74). Используется довольно часто, в особенности в сплайновых кривых: P(t) = (1- t)3P0 + 3t(1- t)2P1 + 3 t2(1-t) P2 + t3P3.
Рис. 74 Геометрический алгоритм для кривой Безье Этот алгоритм позволяет вычислить координаты (х, у) точки кривой Безье по значению параметра t. 1. Каждая сторона контура многоугольника, который проходит по точкам-ориентирам, делится пропорционально значению t. 2. Точки деления соединяются отрезками прямых и образуют новый многоугольник. Количество узлов нового контура на единицу меньше, чем количество узлов предшествующего контура. 3. Стороны нового контура снова делятся пропорционально значению t. И так далее. Это продолжается до тех пор, пока не будет получена единственная точка деления. Эта точка и будет точкой кривой Безье (рис. 75).
Рис. 75 Приведем запись геометрического алгоритма на языке C++: for (i = 0; i <= m; i++) R[i] = P[i]; //формируем вспомогательный массив R[ ] for (j = m; j > 0; j --) for ( i = 0; i < j; i++) R[i] = R[i] + t * (R[i+1] - R[i]); Отсечение отрезка Необходимость отсечь выводимое изображение по границам некоторой области встречается довольно часто. В простейших ситуациях в качестве такой области, как правило, выступает прямоугольник. Ниже рассматривается достаточно простой и эффективный алгоритм отсечения отрезков по границе произвольного прямоугольника. Он заключается в разбиении всей плоскости на 9 областей прямыми, образующими прямоугольник. В каждой из этих областей все точки по отношению к прямоугольнику расположены одинаково. Определив, в какие области попали концы рассматриваемого отрезка, легко понять, где именно необходимо отсечение. Для этого каждой области сообщается 4-битовый код. 4-битовый код: - бит 0 означает, что точка лежит левее прямоугольника, - бит 1 означает, что точка лежит выше прямоугольника, - бит 2 означает, что точка лежит правее прямоугольника, - бит 3 означает, что точка лежит ниже прямоугольника.
Популярное: Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (1051)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |