直線生成演算法
⑴ dda法生成直線的基本原理是什麼為什麼說Bersenham畫圓的演算法效率較高
DDA演算法主要是根據直線公式y = kx + b來推導出來的，其關鍵之處在於如何設定單位步進，即一個方向的步進為單位步進，另一個方向的步進必然是小於1。演算法的具體思路如下：
1. 輸入直線的起點、終點；
2. 計算x方向的間距：△X和y方向的間距：△Y。
3. 確定單位步進，取MaxSteps = max（△X，△Y）; 若△X>=△Y，則X方向的步進為單位步進，X方向步進一個單位，Y方向步進△Y/MaxSteps;否則相反。
4. 設置第一個點的像素值
5. 令循環初始值為1，循環次數為MaxSteps，定義變數x,y，執行以下計算：
a. x增加一個單位步進，y增加一個單位步進
b. 設置位置為（x,y）的像素值
Bresenham演算法是DDA演算法畫線演算法的一種改進演算法。本質上它也是採取了步進的思想。不過它比DDA演算法作了優化，避免了步進時浮點數運算，同時為選取符合直線方程的點提供了一個好思路。首先通過直線的斜率確定了在x方向進行單位步進還是y方向進行單位步進：當斜率k的絕對值|k|<1時，在x方向進行單位步進；當斜率k的絕對值|k|>1時，在y方向進行單位步進。
1. 輸入線段的起點和終點。
2. 判斷線段的斜率是否存在（即起點和終點的x坐標是否相同），若相同，即斜率不存在，
只需計算y方向的單位步進（△Y+1次），x方向的坐標保持不變即可繪制直線。
3. 計算線段的斜率k，分為下面幾種情況處理
a. k等於0，即線段平行於x軸，即程序只需計算x方向的單位步進，y方向的值不變
b. |k|等於1，即線段的x方向的單位步進和y方向的單位步進一樣，皆為1。直接循環△X次計算x和y坐標。
4. 根據輸入的起點和終點的x、y坐標值的大小決定x方向和y方向的單位步進是1還是-1
6. 畫出第一個點。
7. 若|k| <1，設m =0,計算P0，如果Pm>0，下一個要繪制的點為（Xm+單位步進，Ym），
Pm+1 = Pm -2*△Y;
否則要繪制的點為（Xm+單位步進，Ym+單位步進）
Pm+1 = Pm+2*△X-2*△Y；
8. 重復執行第七步△X-1次；
9. 若|k| <1，設m =0,計算Q0，如果Qm>0，下一個要繪制的點為（Xm，Ym+單位步進），
Pm+1 = Pm -2*△X;
否則要繪制的點為（Xm+單位步進，Ym+單位步進）
Pm+1 = Pm+2*△Y-2*△X；
10. 重復執行第9步△Y-1次；
⑵ 有償有償。利用直線生成演算法（DDA演算法或Bresenham演算法）繪制直線，分別處理斜率k的兩種情況
private static int[] insertSort(int[]arr){
if(arr == null || arr.length < 2){
return arr;
}
for(inti=1;i<arr.length;i++){
for(intj=i;j>0;j--){
if(arr[j]<arr[j-1]){
//TODO:
int temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}else{
//接下來是無用功
break;
}
}
}
return arr;
}
⑶ 為什麼說直線生成演算法是二維圖形生成技術的基礎
這很好理解呀，不管畫什麼圖形都是以線為基礎，連填充也是。
能畫出線，還畫不出幾何圖形嗎。
⑷ 計算機圖形學直線生成演算法
我連畫圓的一塊給你吧
需要橡皮筋
橢圓
樹什麼的可以和我說
我是用
c#寫的
using
System;
using
System.Collections.Generic;
using
System.ComponentModel;
using
System.Data;
using
System.Drawing;
using
System.Text;
using
System.Windows.Forms;
namespace
line
{
public
partial
class
Form1
:
Form
{
Graphics
g;
public
Form1()
{
InitializeComponent();
g
=
pictureBox1.CreateGraphics();
}
private
void
button1_Click_1(object
sender,
EventArgs
e)
{
//
g.TranslateTransform(-300,-300);
g.Clear(BackColor);
double
x1,
x2,
y1,
y2;
double
x,
y;
x1
=
System.Convert.ToSingle(textBox1.Text);
y1
=
System.Convert.ToSingle(textBox2.Text);
x2
=
System.Convert.ToSingle(textBox3.Text);
y2
=
System.Convert.ToSingle(textBox4.Text);
x
=
x1;
double
k
=
(y1
-
y2)
/
(x1
-
x2);
Color
color1
=
Color.FromArgb(255,
0,
0);
//定義顏色
Brush
bru1
=
new
SolidBrush(color1);//定義筆
Color
color2
=
Color.FromArgb(0,
255,
0);
//定義顏色
Brush
bru2
=
new
SolidBrush(color2);//定義筆
Pen
pen1
=
new
Pen(bru1,
1);
Pen
pen2
=
new
Pen(bru2,
1);
while
(x
<
x2)
{
//
textBox3.Text
=
System.Convert.ToString(k);
y
=
(double)k
*
(x
-
x1)
+
y1;
double
a;
a=y%1;
float
xx
=
Convert.ToSingle(x);
float
yy
=
Convert.ToSingle(y);
if
(a
>
0.5)
{
g.DrawLine(pen1,
xx,
yy,
xx,yy+1);
}
else
{
g.DrawLine(pen2,
xx,
yy,
xx,
yy+1);
}
x++;
}
//g.DrawLine(p,10,10,100,100);
}
private
void
button2_Click(object
sender,
EventArgs
e)
{
g.TranslateTransform(300,
300);
g.Clear(BackColor);
float
r;//r為圓的圓心
r
=System.Convert.ToSingle(textBox6.Text);
Color
color1
=
Color.FromArgb(255,
0,
0);
//定義顏色
Brush
bru1
=
new
SolidBrush(color1);//定義筆
Color
color2
=
Color.FromArgb(0,
255,
0);
//定義顏色
Brush
bru2
=
new
SolidBrush(color2);//定義筆
Pen
pen1
=
new
Pen(bru1,1);
Pen
pen2
=
new
Pen(bru2,
1);
float
x
=
0;
float
y
=
r;
while
(x
<r+3)
{
y
=
(float)System.Math.Sqrt(r
*
r
-
x
*
x);
float
a;
a
=
y
%
1;
y
=
y
-
a;
if
(a
>
0.5)
{
g.DrawLine(pen1,
x,
y,
x,
y+1);
g.DrawLine(pen1,
-x,
y,
-x,
y
+
1);
g.DrawLine(pen1,
x,
-y,
x,
-y
+
1);
g.DrawLine(pen1,
-x,
-y,
-x,
-y
+
1);
}
else
{
g.DrawLine(pen2,
x,
y,
x,
y+1);
g.DrawLine(pen2,
-x,
y,
-x,
y
+
1);
g.DrawLine(pen2,
x,-
y,
x,-
y
+
1);
g.DrawLine(pen2,
-x,
-y,-
x,
-y
+
1);
}
x++;
}
g.TranslateTransform(-300,
-300);
}
private
void
button3_Click(object
sender,
EventArgs
e)
{
}
private
void
comboBox1_SelectedIndexChanged(object
sender,
EventArgs
e)
{
switch
(comboBox1.Text)
{
case
"畫圓":
{
textBox1.Visible
=
false;
textBox2.Visible
=
false;
textBox3.Visible
=
false;
textBox4.Visible
=
false;
textBox5.Visible
=
true;
textBox6.Visible
=
true;
textBox7.Visible
=
false;
textBox8.Visible
=
false;
label1.Visible
=
false;
label2.Visible
=
false;
label3.Visible
=
false;
label4.Visible
=
false;
label5.Visible
=
true;
label6.Visible
=
true;
label7.Visible
=
false;
label8.Visible
=
false;
label9.Visible
=
true;
button1.Visible
=
false;
button2.Visible
=
true;
button3.Visible
=
false;
break;
}
case"畫線":
{
textBox1.Visible
=
true;
textBox2.Visible
=
true;
textBox3.Visible
=
true;
textBox4.Visible
=
true;
textBox5.Visible
=
false;
textBox6.Visible
=
false;
textBox7.Visible
=
false;
textBox8.Visible
=
false;
label1.Visible
=
true;
label2.Visible
=
true;
label3.Visible
=
true;
label4.Visible
=
true;
label5.Visible
=
false;
label6.Visible
=
false;
label7.Visible
=
false;
label8.Visible
=
false;
label9.Visible
=
false;
button1.Visible
=
true;
button2.Visible
=
false;
button3.Visible
=
false;
break;
}
case"畫橢圓":
{
textBox1.Visible
=
false;
textBox2.Visible
=
false;
textBox3.Visible
=
false;
textBox4.Visible
=
false;
textBox5.Visible
=
false;
textBox6.Visible
=
false;
textBox7.Visible
=
true;
textBox8.Visible
=
true;
label1.Visible
=
false;
label2.Visible
=
false;
label3.Visible
=
false;
label4.Visible
=
false;
label5.Visible
=
false;
label6.Visible
=
false;
label7.Visible
=
true;
label8.Visible
=
true;
label9.Visible
=
false;
button1.Visible
=
false;
button2.Visible
=
false;
button3.Visible
=
true;
break;
}
}
}
}
}
⑸ 計算機圖形學中直線的生成演算法
/* DDA演算法 */
#include "Conio.h"
#include "graphics.h"
#define closegr closegraph
void initgr(void) /* BGI初始化 */
{int gd=DETECT,gm=0; /* 和gd=VGA,gm=VGAHI是同樣效果 */
registerbgidriver(EGAVGA_driver);/* 注冊BGI驅動後可以不需要.BGI文件的支持運行 */
initgraph(&gd,&gm,"");
}
void DDALine(int x0,int y0,int x1,int y1,int color)
{
int x;
float dx,dy,y,k;
dx=x1-x0 ;
dy=y1-y0;
k=dy/dx;
y=y0;
for(x=x0;x<=x1;x++)
{
putpixel(x,(int)(y+0.5),color);
y=y+k;
}
}
main()
{initgr(); /* BGI初始化 */
DDALine(100,100,200,200,6) ;
getch(); /* 暫停一下，看看前面繪圖代碼的運行結果 */
closegr(); /* 恢復TEXT屏幕模式 */
}
⑹ 描述Bresenham直線生成演算法，並導出其在第一象限內的遞推公式。
看看 那本計算機圖形學 和清芳的
介紹的很清楚
⑺ 直線和圓的生成演算法
直線和圓的像素級生成演算法2008-05-31 16:42直線的像素級生成演算法：
光柵掃描顯示器，其顯示屏是由許多被稱為像素的點組成。顯示器顯示的圖形或圖像就是通過這些像素的亮與不亮（或顏色不同）的各種組合而形成的。
像素級生成方法：如果要生成一條曲線，逐點地選擇那些距離曲線最近的像素並將其點亮，這就是像素級（或點）生成演算法。
優點：1. 生成的曲線誤差小，精度高。一般所顯示的像素與實際曲線之間的距離一般不大於二分之一個像素單位。
2. 演算法只使用整數運算（至少在主循環內只使用整數運算），因而執行速度快。
bresenham演算法：
偽代碼：
在(x1,y1)到(x2,y2)之間畫一條直線
dx 是x到終點橫坐標的距離
dy 是y到終點縱坐標的距離
ix 是dx的絕對值
iy 是dy的絕對值
inc是dx和dy中較大的那個
plot是是否要畫一個點的標志位，boolean變數
plotx 是當前點所在的橫坐標
ploty 是當前點所在的縱坐標
plotx = x1
ploty = y1
x = 0
y = 0
在 plotx,ploty畫一個點——起點
for i = 0 to inc 增量1
x += ix
y += iy
plot = false
if x > inc then
plot = true
x -= inc
if dx > 0 then plotx ++
if dx < 0 then plotx --
if y > inc then
plot = true
y -= inc
if dy > 0 then ploty ++
if dy < 0 then ploty --
if plot == true then 在（plotx,ploty）處畫點
c代碼：
void draw_line1(pnt s, pnt e)
{
int plotx, ploty; //當前點橫縱坐標
plotx = s.x;
ploty = s.y;
int x, y;
x = 0;
y = 0;
int dx, dy; //x,y到終點橫、縱坐標的距離
dx = e.x - s.x;
dy = e.y - s.y;
int ix, iy; //dx,dy的絕對值
ix = abs(dx);
iy = abs(dy);
int inc = (dx > dy ? dx : dy);
char plot = FALSE;
for(int i=0; i<inc; ++i)
{
x += ix;
y += iy;
plot = FALSE;
if(x > inc)
{
plot = TRUE;
x -= inc;
if (dx > 0)
plotx++; //當前點加1
if (dx < 0)
plotx--;
}
if(y > inc)
{
plot = TRUE;
y -= inc;
if(dy > 0)
ploty++;
if(dy < 0)
ploty--;
}
if(plot == TRUE)
{
int i = ploty*WIDTH + 3*plotx;
image[i] = 0;
image[i+1] = 0;
image[i+2] = 0;
}
}
LCD_SetFrameBufferAddress(image);
}
最快的像素級圓生成演算法：
形式描述：
x = 0; y = R;
d = -R/2;
if R is even then goto EvNoIt;
setpixel(x, y);
LOOP: x = x + 1;
if d<0 then d=d+x;
else {
y=y-1;
d=d+x-y;
if x>y then stop;
}
setpixel(x, y);
EvNoIt: x=x+1;
if d<0 then d=d+x+1;
else {
y=y-1;
d=d+x-y+1;
if x>y then stop;
}
setpixel(x, y);
goto LOOP;
C代碼：
void draw_circle(pnt c, int r)
{
int x,y,d;
x = 0;
y = r;
d = -r/2;
while(x<y)
{
if(r%2 == 0)
//第一象限
setpixel(c.x+x, c.y+y);
setpixel(c.y+y, c.x+x);
//第二象限
setpixel(c.x+x, c.y-y);
setpixel(c.y+y, c.x-x);
//
setpixel(c.x-x, c.y+y);
setpixel(c.y-y, c.x+x);
//
setpixel(c.x-x, c.y-y);
setpixel(c.y-y, c.x-x);
if(r%2 == 1)
{
x += 1;
if(d < 0)
d += x + 1;
else
{
y -= 1;
d += x - y + 1;
}
//第一象限
setpixel(c.y+y, c.x+x);
setpixel(c.x+x, c.y+y);
//第二象限
setpixel(c.x+x, c.y-y);
setpixel(c.y+y, c.x-x);
//
setpixel(c.x-x, c.y+y);
setpixel(c.y-y, c.x+x);
//
setpixel(c.x-x, c.y-y);
setpixel(c.y-y, c.x-x);
}
x += 1;
if(d < 0)
d += x;
else
{
y -= 1;
d += x - y;
}
//第一象限
setpixel(c.y+y, c.x+x);
setpixel(c.x+x, c.y+y);
//第二象限
setpixel(c.x+x, c.y-y);
setpixel(c.y+y, c.x-x);
//
setpixel(c.x-x, c.y+y);
setpixel(c.y-y, c.x+x);
//
setpixel(c.x-x, c.y-y);
setpixel(c.y-y, c.x-x);
}
LCD_SetFrameBufferAddress(image);
}
⑻ WIN-TC 直線生成演算法問題
WIN-TC下運行通過
http://hi..com/_586/blog/item/de80dfce15f1310092457ee8.html