Связь и интернет Архив Программирование
   
Сделать стартовойСделать закладку            
   ПОИСК  
   
Главная / Алгоритмы / Графика / Рисование простых графических объектов /
8  Perl
8  PHP
8  JavaScript
8  HTML
8  DHTML
8  XML
8  CSS
8  C / C++
8  Pascal и Delphi
8  Турбо Ассемблер
8  MySQL
8  CASE-технологии
8  Алгоритмы
8  Python
8  Обратная связь
8  Гостевая книга
Новости о мире


Рисование окружности - Программирование от RIN.RU
Рисование окружности

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


Алгоритм Брезенхема


Для простоты и без ограничения общности рассмотрим генерацию 1/8 окружности, центр которой лежит в начале координат. Остальные части окружности могут быть получены последовательными отражениями (использованием симметрии точек на окружности относительно центра и осей координат).


Окружность с центром в начале координат описывается уравнением:


X2 + Y2 = R2




Алгоритм Брезенхема пошагово генерирует очередные точки окружности, выбирая на каждом шаге для занесения пиксела точку растра Pi(Xi,  Yi), ближайшую к истинной окружности, так чтобы ошибка:


Ei(Pi)    =   (Xi2   +   Yi2)   -   R2




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


Рассмотрим генерацию 1/8 окружности по часовой стрелке, начиная от точки X=0, Y=R.


Проанализируем возможные варианты занесения i+1-й точки, после занесения i-й.



Рис. 1: Варианты расположения очередного пиксела окружности




При генерации окружности по часовой стрелке после занесения точки (Xi, Yi) следующая точка может быть либо Pg = (Xi+1, Yi) - перемещение по горизонтали, либо Pd = (Xi+1, Yi-1) - перемещение по диагонали, либо Pv = (Xi, Yi-1) - перемещение по вертикали.


Для этих возможных точек вычислим и сравним абсолютные значения разностей квадратов расстояний от центра окружности до точки и окружности:


|Dg|
=
| (X+1)2
+
Y2
-
R2 |
|Dd|
=
| (X+1)2
+
(Y-1)2
-
R2 |
|Dv|
=
| X2 /td>
+
(Y-1)2
-
R2 |




Выбирается и заносится та точка, для которой это значение минимально.


Выбор способа расчета определяется по значению Dd. Если Dd < 0, то диагональная точка внутри окружности. Это варианты 1-3 (см. рис. 0.1б). Если Dd > 0, то диагональная точка вне окружности. Это варианты 5-7. И, наконец, если Dd = 0, то диагональная точка лежит точно на окружности. Это вариант 4. Рассмотрим случаи различных значений Dd в только что приведенной последовательности.


Случай Dd < 0


Здесь в качестве следующего пиксела могут быть выбраны или горизонтальный - Pg или диагональный - Pd.


Для определения того, какой пиксел выбрать Pg или Pd составим разность:


di

=
|Dg| - |Dd| =
|(X+1)2 + Y2 - R2| - |(X+1)2 + (Y-1)2 - R2|




И будем выбирать точку Pg при di ? 0, в противном случае выберем Pd.


Рассмотрим вычисление di для разных вариантов.


Для вариантов 2 и 3:


Dg ? 0 и Dd < 0, так как горизонтальный пиксел либо вне, либо на окружности, а диагональный внутри.


di = (X+1)2 + Y2 - R2 + (X+1)2 + (Y-1)2 - R2;




Добавив и вычтя (Y-1)2 получим:


di = 2 ·[(X+1)2 + (Y-1)2 - R2] + 2·Y - 1




В квадратных скобках стоит Dd, так что


di = 2 ·(Dd + Y) - 1




Для варианта 1:


Ясно, что должен быть выбран горизонтальный пиксел Pg. Проверка компонент di показывает, что Dg < 0 и Dd < 0, причем di < 0, так как диагональная точка больше удалена от окружности, т.е. по критерию di < 0 как и в предыдущих случаях следует выбрать горизонтальный пиксел Pg, что верно.


Случай Dd > 0


Здесь в качестве следующего пиксела могут быть выбраны или диагональный - Pd или вертикальный Pv.


Для определения того, какую пиксел выбрать Pd или Pv составим разность:


si

=
|Dd| - |Dv| =
|(X+1)2 + (Y-1)2 - R2| - |X2 + (Y-1)2 - R2|




Если si ? 0, то расстояние до вертикальной точки больше и надо выбирать диагональный пиксел Pd, если же si > 0, то выбираем вертикальный пикселPv.


Рассмотрим вычисление si для разных вариантов.


Для вариантов 5 и 6:


Dd > 0 и Dv ? 0, так как диагональный пиксел вне, а вертикальный либо вне либо на окружности.


si = (X+1)2 + (Y-1)2 - R2 + X2 + (Y-1)2 - R2;




Добавив и вычтя (X+1)2 получим:


si = 2 ·[(X+1)2 + (Y-1)2 - R2] - 2·X - 1




В квадратных скобках стоит Dd, так что


si = 2 ·(Dd - X) - 1




Для варианта 7:


Ясно, что должен быть выбран вертикальный пиксел Pv. Проверка компонент si показывает, что Dd > 0 и Dv > 0, причем si > 0, так как диагональная точка больше удалена от окружности, т.е. по критерию si > 0 как и в предыдущих случаях следует выбрать вертикальный пиксел Pv, что соответствует выбору для вариантов 5 и 6.


Случай Dd = 0


Для компонент di имеем: Dg > 0 и Dd = 0, следовательно по критерию di > 0 выбираем диагональный пиксел.


С другой стороны, для компонент si имеем: Dd = 0 и Dv < 0, так что по критерию si ? 0 также выбираем диагональный пиксел.
Итак:


Dd < 0
di ? 0 - выбор горизонтального пиксела Pg


di > 0 - выбор диагонального пиксела Pd
Dd > 0


si ? 0 - выбор диагонального пиксела Pd


si > 0 - выбор вертикального пиксела Pv


Dd = 0


выбор диагонального пиксела Pd.


Выведем рекуррентные соотношения для вычисления Dd для (i+1)-го шага, после выполнения i-го.


  1. Для горизонтального шага к Xi+1, Yi


    Xi+1 = Xi + 1
    Yi+1 = Yi
    Ddi+1 = (Xi+1+1)2 + (Yi+1-1)2 - R2 =
    Xi+12 + 2·Xi+1 + 1 + (Yi+1-1)2 - R2 =
    (Xi+1)2 + (Yi-1)2 - R2 + 2·Xi+1 + 1 =
    Ddi + 2·Xi+1 + 1


  2. Для диагонального шага к Xi+1, Yi-1


    Xi+1 = Xi + 1
    Yi+1 = Yi - 1
    Ddi+1 = Ddi + 2 ·Xi+1 - 2 ·Yi+1 + 2

  3. Для вертикального шага к Xi, Yi-1


    Xi+1 = Xi
    Yi+1 = Yi - 1
    Ddi+1 = Ddi - 2 ·Yi+1 + 1




В Приложении 5 приведена подпрограмма V_circle, реализующая описанный выше алгоритм и строящая дугу окружности в первой четверти. Начальная инициализация должна быть:


X= 0
Y= R
Dd = (X+1)2 + (Y-1)2 - R2 = 1 + (R-1)2 - R2 = 2*(1 - R)


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


В Приложении приведены подпрограмма V_BRcirc, реализующая описанный выше алгоритм и строящая дугу окружности во втором октанте с последующим симметричным занесением пикселов. Эта процедура может строить и 1/4 окружности. Подробнее см. текст Приложения. Там же приведена более короткая подпрограмма, строящая 1/8 окружности методом Мичнера [], (том 1, стр. 152). Остальная часть окружности строится симметрично.


Приложение 4. Процедуры генерации окружности


В данном приложении помещены процедуры генерации окружностей по алгоритму Брезенхема и Мичнера, а также программа T_Circle для тестирования данных процедур.


/*--------------------------------------------------- V_Circle
* Подпрограммы для генерации окружности
* Pixel_circle - занесение пикселов с учетом симметрии
* V_BRcirc - генерирует окружность по алгоритму
* Брезенхема.
* V_MIcirc - генерирует окружность по алгоритму
* Мичнера.
*/


#include <graphics.h>


/*----------------------------------------------- Pixel_circle
* Заносит пикселы окружности по часовой стрелке
*/


static void Pixel_circle (xc, yc, x, y, pixel)
int xc, yc, x, y, pixel;
{
putpixel(xc+x, yc+y, pixel);
putpixel(xc+y, yc+x, pixel);
putpixel(xc+y, yc-x, pixel);
putpixel(xc+x, yc-y, pixel);
putpixel(xc-x, yc-y, pixel);
putpixel(xc-y, yc-x, pixel);
putpixel(xc-y, yc+x, pixel);
putpixel(xc-x, yc+y, pixel);
} /* Pixel_circle */




/*--------------------------------------------------- V_BRcirc
* Генерирует 1/8 окружности по алгоритму Брезенхема
*
* Процедура может строить 1/4 окружности.
* Для этого надо цикл while заменить на for (;;)
* и после Pixel_circle проверять достижение конца по условию
* if (y <= end) break;
* Где end устанавливается равным 0
* В этом случае не нужен и последний оператор
* if (x == y) Pixel_circle (xc, yc, x, y, pixel);
* Генерацию 1/8 можно обеспечить задав end = r / sqrt (2)
*/


void V_BRcirc (xc, yc, r, pixel)
int xc, yc, r, pixel;
{ int x, y, z, Dd;
x= 0; y= r; Dd= 2*(1-r);
while (x < y) {
Pixel_circle (xc, yc, x, y, pixel);
if (!Dd) goto Pd;
z= 2*Dd - 1;
if (Dd > 0) {
if (z + 2*x <= 0) goto Pd; else goto Pv;
}
if (z + 2*y > 0) goto Pd;
Pg: ++x; Dd= Dd + 2*x + 1; continue; /* Горизонт */
Pd: ++x; --y; Dd= Dd + 2*(x-y+1); continue; /* Диагонал */
Pv: --y; Dd= Dd - 2*y + 1; /* Вертикал */
}
if (x == y) Pixel_circle (xc, yc, x, y, pixel);
} /* V_BRcirc */




/*--------------------------------------------------- V_MIcirc
* Генерирует 1/8 окружности по алгоритму Мичнера
*/


void V_MIcirc (xc, yc, r, pixel)
int xc, yc, r, pixel;
{ int x, y, d;
x= 0; y= r; d= 3 - 2*r;
while (x < y) {
Pixel_circle (xc, yc, x, y, pixel);
if (d < 0) d= d + 4*x + 6; else {
d= d + 4*(x-y) + 10; --y;
}
++x;
}
if (x == y) Pixel_circle (xc, yc, x, y, pixel);
} /* V_MIcirc */








/*=============================================== T_CIRCLE.C
*
* ТЕСТ ГЕНЕРАЦИИ ОКРУЖНОСТЕЙ
*
* Запрашивает ввод четырех чисел - координат центра,
* радиуса и цвета построения: Xc Yc R Pix
*
* Затем строит заданную окружность по алгоритму Брезенхема
* и концентрично с ней с радиусом, уменьшенным на 2, и
* номером цвета, уменьшенным на 1, выдает окружность по
* алгоритму Мичнера.
*
* При вводе Xc < 0 программа прекращает работу
*/


#include <graphics.h>
#include <stdio.h>
#include "V_CIRCLE.C"




/*-------------------------------------------- MAIN T_CIRCLE.C
*/
void main (void)
{
int ii, Xc=300, Yc=240, R=238, Pix=14;
int gdriver = DETECT, gmode;


initgraph(&gdriver, &gmode, "c:\tc\bgi");
if ((ii= graphresult()) != grOk) {
printf ("Err=%d\n", ii); goto all;
}
setbkcolor(0);
cleardevice();


for (;;) {
gotoxy (1,1);
printf(" \r");
printf("Xc, Yc, R, Pix= (%d %d %d %d) ? ", Xc,Yc,R,Pix);
scanf ("%d%d%d%d", &Xc, &Yc, &R, &Pix);
if (Xc < 0) break;
V_BRcirc (Xc, Yc, R, Pix);
V_MIcirc (Xc, Yc, R-2, Pix-1);
}
all:
closegraph();
}




Исходники этого алгоритма, взятые из других источников



void Circle(int x, int y, int r,unsigned char color)
{
int x1,y1,yk = 0;
int sigma,delta,f;


x1 = 0;
y1 = r;
delta = 2*(1-r);


do
{
PutPixel(x+x1,y+y1,color);
PutPixel(x-x1,y+y1,color);
PutPixel(x+x1,y-y1,color);
PutPixel(x-x1,y-y1,color);


f = 0;
if (y1 < yk)
break;
if (delta < 0)
{
sigma = 2*(delta+y1)-1;
if (sigma <= 0)
{
x1++;
delta += 2*x1+1;
f = 1;
}
}
else
if (delta > 0)
{
sigma = 2*(delta-x1)-1;
if (sigma > 0)
{
y1--;
delta += 1-2*y1;
f = 1;
}
}
if (!f)
{
x1++;
y1--;
delta += 2*(x1-y1-1);
}
}
while(1);
}


На Паскале:



Procedure Circle(x,y,rr:integer);
var xi,yi,r,di,lim,s,ss:integer;
label 1,2,3,4,10,20,30;
Begin
r:=rr;
xi:=0; yi:=r; di:=2*(1-r); lim:=0;
1: SetPixel(xi+x,yi+y);
SetPixel(xi+x,-yi+y);
SetPixel(-xi+x,yi+y);
SetPixel(-xi+x,-yi+y);
if yi<limthen goto 4;
if di<0then goto 2;
if di>0then goto 3;
if di=0 then goto 20;
2: s:=2*di+2*yi-1;
if s<=0then goto 10;
if s>0then goto 20;
3: s:=2*di+2*xi-1;
if s<=0then goto 20;
if s>0then goto 30;
10:xi:=xi+1;
di:=di+2*xi+1;
goto 1;
20:xi:=xi+1;
yi:=yi-1;
di:=di+2*xi-2*yi+2;
goto 1;
30:yi:=yi-1;
di:=di-2*yi+1;
goto 1;4:
end;




 8  Комментарии к статье  8  Обсудить в форуме  8  Обсудить в чате

 
  
  
    Copyright ©  RIN 2003 - 2004      * Обратная связь