Автор работы: Пользователь скрыл имя, 08 Декабря 2013 в 13:49, лабораторная работа
Цель работы: реализация алгоритмов построения отрезков по методу цифрового дифференциального анализатора (ЦДА), алгоритмов Брезенхема (действительного, целочисленного, оптимизированного и с устранением ступенчатости) и Ву, исследование их характеристик и сравнение полученных результатов.
При этом значение интенсивности для высвечивания очередного пиксела должно иметь значение E(f/2DX), причем деление производится целочисленное.
Алгоритм Ву заключается в следующем: при рисовании линии обычным способом мы с каждым шагом вдоль основной оси ставятся две точки вдоль неосновной. При установке двух точек их интенсивность подбирается пропорционально расстоянию от центра точки до идеальной линии. Чем больше удалена точка от идеальной линии, тем меньше ее интенсивность Значения интенсивности двух пикселей всегда дают в сумме единицу, т.е. это интенсивность одного пикселя, в точности попавшего на идеальную линию. Такое распределение придаст линии одинаковую интенсивность на всем ее протяжении, создавая при этом иллюзию, что точки расположены вдоль линии не по две, а по одной.
Ход работы:
Для реализации алгоритмов была написана программа на языке C++ в среде C++ Builder. Были получены результаты, изображенные на картинках, для различных масштабов, а также замерены приблизительные временные характеристики алгоритмов на контрольном примере при масштабе N=18.
Время выполнения на контрольном примере: 0-1.
Время выполнения на контрольном примере: 1-3.
Время выполнения на контрольном примере: 1-2.
Время выполнения на контрольном примере: 1-2.
Время выполнения на контрольном примере: 2-7.
Время выполнения на контрольном примере: 5-10.
Листинг программы:
//----вспомогательные
int sign(int z) // определение знака числа
{
return z<0? -1 : (z==0? 0 : 1);
}
double round(double z) // округление
{
return ((z-floor(z))>=0.5) ? ceil(z):floor(z);
}
int getCoord(int z) // целочисленное деление на размер клетки
{
return z/N;
}
void swap(double *x, double *y) // обмен значениями, дробный и целочисленный
{
double z = *x;
*x = *y;
*y = z;
}
void swap(int *x, int *y)
{
int z = *x;
*x = *y;
*y = z;
}
double max(double x, double y) // максимум, дробный целочисленный3,,33
{
return x<y? x: y;
}
int max(int x, int y)
{
return x<y? x: y;
}
//-----вспомогательные визуальные функции-----------------------
void clearLog(){if (FLog->Visible) FLog->Memo1->Clear(); }
bool showError()
{
MessageBeep(100);
FPoints->Caption="Этот алгоритм пока не реализован.";
return false;
}
//----------------------------
void inLog(String s)
{
if (FLog->Visible) FLog->Memo1->Lines->Add(s);
if (FPoints->cboxPause->Checked) ShowMessage("Пауза");
}
void inLog(String s, double x)
{
if (FLog->Visible) FLog->Memo1->Lines->Add(s+" = "+FloatToStr(x));
if (FPoints->cboxPause->Checked) ShowMessage("Пауза");
}
void inLog(String s, double x, double y)
{
if (FLog->Visible) FLog->Memo1->Lines->Add(s+" = "+FloatToStr(x)+" ; "+FloatToStr(y));
if (FPoints->cboxPause->Checked)
}
//----------------------------
void putPixel(TCanvas *canvas,int x,int y, int percent = 100)
{ // закрашивание пикселя в координатах x и y оттенка percent
TColor color;
if (percent == -1) // фоновый цвет
color = clBtnFace;
else
if (percent != 100){ // смешивание цвета
int l_col = ColorToRGB(FPoints->
int f_col = ColorToRGB(clBtnFace);
float lr = GetRValue(l_col); float fr = GetRValue(f_col);
float lg = GetGValue(l_col); float fg = GetGValue(f_col);
float lb = GetBValue(l_col); float fb = GetBValue(f_col);
int rcol=percent*(fr-lr)/100.0;
int gcol=percent*(fg-lg)/100.0;
int bcol=percent*(fg-lg)/100.0;
color = RGB(rcol,gcol,bcol);
} else
color = FPoints->ColorDialog1->Color;
if (N==1) // для одиночного пикселя
canvas->Pixels[x][y] = color;
else
{ // заполнение клетки цветом, с 4х сторон, чтоб наверняка
canvas->Brush->Color = color;
canvas->FloodFill(x*N+1,y*N+1,
canvas->FloodFill((x+1)*N-2,y*
canvas->FloodFill(x*N+1,(y+1)*
canvas->FloodFill((x+1)*N-2,(
}
}//---------------------------
void paintGrid(TCanvas *canvas) // отрисовка сетки
{
if (N==1) return;
canvas->Pen->Color = clBlack;
canvas->Pen->Width = 1;
for (int i = N; i<=W; i+=N)
{
canvas->MoveTo(i,0);
canvas->LineTo(i,H);
}
for (int i = N; i<=H; i+=N)
{
canvas->MoveTo(0,i);
canvas->LineTo(W,i);
}
}
//----------------------------
void paintOrdinaryLine(TCanvas* canvas)
{
int time = timeGetTime();
inLog("Новая обычная линия");
inLog("Координаты начала",x1,y1);
inLog("Координаты конца",x2,y2);
canvas->Pen->Color = FPoints->ColorDialog1->Color;
canvas->Pen->Width = N;
canvas->MoveTo(x1*N+N/2,y1*N+
canvas->LineTo(x2*N+N/2,y2*N+
FPoints->OutTime->Caption=
}
//----------------------------
void paintBrezFLine(TCanvas* canvas)
{
int time = timeGetTime();
inLog("Новая линия, вещественный алгоритм Брезенхема");
inLog("Координаты начала",x1,y1);
inLog("Координаты конца",x2,y2);
int dy = y2-y1;
int dx = x2-x1;
inLog("Глобальные приращения",dx,dy);
int hy = sign(dy);
int hx = sign(dx);
inLog("Локальные приращения",hx,hy);
int Ly = abs(dy);
int Lx = abs(dx);
double m = 0;
inLog("Тангенс",m);
bool onX = true;
if (Ly>Lx){
m= (!Ly) ? 0 : 1.0*Lx/Ly;
onX=false;
int D = Ly;
Ly = Lx;
Lx = D;
} else {
m= (!Lx) ? 0 : 1.0*Ly/Lx;
onX = true;
}
int x=x1,y=y1;
putPixel(canvas,x,y);
inLog("Точка в координатах",x,y);
double f = m-0.5;
inLog("f",m);
for (int i=1; i<=Lx; i++){
if (f>=0){
onX? y+=hy : x+=hx;
onX? x+=hx : y+=hy;
f--;
} else {
onX? x+=hx : y+=hy;
}
f+=m;
inLog("Ошибка",f);
inLog("Точка в координатах",x,y);
putPixel(canvas,x,y);
}
inLog("Конец линии");
FPoints->OutTime->Caption=
}
void paintWuLine(TCanvas* canvas)
{
int time = timeGetTime();
inLog("Новая линия, алгоритм Ву");
inLog("Координаты начала",x1,y1);
inLog("Координаты конца",x2,y2);
int dy = y2-y1;
int dx = x2-x1;
inLog("Глобальные приращения",dx,dy);
int x=x1,y=y1;
int hy = sign(dy);
int hx = sign(dx);
inLog("Локальные приращения",hx,hy);
int Ly = abs(dy);
int Lx = abs(dx); // шаги по основной и дополнительной оси
int i,j; // длины по основной и дополнительной
int kx,ky; // смещения второй оси
int oi,oj;
bool onX = Lx>Ly;
if (onX){ // определяем основную и дополнительную ось
i=hx;
j=0;
oi=Lx;
oj=Ly; // основная x
kx=0;
ky=hy;
} else {
i=0;
j=hy;
oi=Ly;
oj=Lx; // основная y
kx=hx;
ky=0;
// if (hx==1) kx=hx;
}
int In = 100; // число уровней интенсивности
int dx1 = In*oi;
int dy1 = In*oj;
int f=oi*In; // начальная ошибка
inLog("Начальная ошибка",f);
inLog("Предел ошибки",2*dx1-2*dy1);
inLog("Интенсивнось",In);
int firstColor = In/2;
putPixel(canvas,x,y,
putPixel(canvas,x+kx,y+ky,100-
inLog("Первая точка в координатах",x,y);
inLog("Цвет, %",firstColor);
inLog("Вторая точка в координатах",x+kx,y+ky);
inLog("Цвет, %",100-firstColor);
for (int k=1; k<=oi; k++){ // цикл по пикселям основной оси
if (f>=2*dx1-2*dy1){ // если ошибка больше
x+=hx;
y+=hy;
inLog("Корректировка, ошибка",f);
f=f-2*dx1+2*dy1;
} else {
x+=i;
y+=j;
f+=2*dy1;
}
int color = 100*(f/(2*oi))/In;
if (color==0) color=100;
putPixel(canvas,x,y,color);
putPixel(canvas,x+kx,y+ky,(
inLog("Первая точка в координатах",x,y);
inLog("Цвет, %",color);
inLog("Вторая точка в координатах",x+kx,y+ky);
inLog("Цвет, %",100-color);
inLog("Ошибка",f);
}
inLog("Конец линии");
FPoints->OutTime->Caption=
}
//----------------------------
void paintBrezOLine(TCanvas* canvas)
{
int time = timeGetTime();
inLog("Новая линия, оптимизированный алгоритм Брезенхема");
inLog("Координаты начала",x1,y1);
inLog("Координаты конца",x2,y2);
int dy = y2-y1;
int dx = x2-x1;
inLog("Глобальные приращения",dx,dy);
// начальная точка
int x=x1,y=y1;
putPixel(canvas,x,y);
int hx = sign(dx);
int hy = sign(dy);
inLog("Локальные приращения",hx,hy);
double Ly = abs(dy)+1;
double Lx = abs(dx)+1;
int D; // целочисленное приращение
double m; // ошибка
if (Lx>Ly){ // определяем основную и дополнительную ось
D=Lx/Ly; // минимальное кол-во пикселей в отрезке
m=abs(Lx)%abs(Ly)/Ly; // ошибка
} else { // основная y
D=Ly/Lx;
m=abs(Ly)%abs(Lx)/Lx;
}
double f = m;
inLog("Ошибка",f);
int k=0; // счетчик пискелей отрезка
// для количества отрезков по дополнительной оси
for (int n = 0; n<((Lx>Ly)?Ly:Lx); n++)
{
k=0;
f+=m;
if (f>1){
f--;
k--;
inLog("Дополнительный пиксель");
}
if (Lx>Ly){
for (k; k<abs(hx*D); k++){
}
} else {
for (k; k<abs(hy*D); k++){
}
}
inLog("Ошибка",f);
(Lx>Ly)? y+=hy : x+=hx;
}
inLog("Конец линии");
FPoints->OutTime->Caption=
}
//----------------------------
void paintBrezILine(TCanvas* canvas)
{
int time = timeGetTime();
inLog("Новая линия, целочисленный алгоритм Брезенхема");
inLog("Координаты начала",x1,y1);
inLog("Координаты конца",x2,y2);
int dy = y2-y1;
int dx = x2-x1;
inLog("Глобальные приращения",dx,dy);
int x=x1,y=y1;
putPixel(canvas,x,y);
int hy = sign(dy);
int hx = sign(dx);
inLog("Локальные приращения",hx,hy);
int Ly = abs(dy);
int Lx = abs(dx);
int i,j; // шаги по основной и дополнительной оси
int oi,oj; // длины по основной и дополнительной
if (Lx>Ly){ // определяем основную и дополнительную ось
Информация о работе Реализация алгоритмов построения отрезков с помощью различных алгоритмов