画直线算法

30 April 2021 - 5 mins read time
Tags: 计算机图形学

DDA算法

David F. Rogers 描述：x、y每次总长度/总次数地增加

Length =max( |xs- xe |, | ys-ye | )
StepX = ( xe -xs) / Length; 
StepY = ( ye -ys) / Length; 
x = xs，y = ys; //首点 
for( i = 1; i≤ Length; i++){
	WritePixel (Round(x), Round(y) ,value)); 
	x = x + StepX; 
	y = y + StepY; 
} 

James D.Foley 描述：每次 x方向增加 1，y方向增加 k

int xs,ys, xe,ye,value;   //start/end端点，设 0≤ k≤ 1
double k =(xe-xs)/(ye-ys); 
double y =ys; 
for ( x=xs; x<=xe; x++) { 
	WritePixel(x,Round(y),value); 
	y+=k; 
} 

任意方向：

int xs,ys, xe,ye,value, ix, iy; //初始显示的光点坐标
int Length =max( |xs- xe |, | ys-ye | )
int k=| ys-ye |/|xs- xe |；
if ( | ys-ye |<=|xs- xe |) { //X改变长度更长，则k<=1
    ix= Round(xs); //初始显示的点的x坐标 
    iy= Round(ys+k*(ix-xs)); //y点校正 
    for (n=0; n< Length; n++) { 
        WritePixel(ix, iy, value); 
        ix+=isign(xe- xs); //x增加0 or 1 or -1，取决于符号
        iy+=k; //y增加k
    }
} 
else { 		//X改变长度更长，则k>1 
    iy= Round(ys); 
    ix= Round(xs+k*(iy-ys)); 
    for (n=0; n< Length; n++) { 
        WritePixel (ix, iy, value); 
        iy+=isign(ye- ys); 
        ix+=k; 
    } 
}

Bresenham算法

第一个八分象限：

def BresenhamLine(x1, y1, x2, y2, color):
dx = x2 - x1
dy = y2 - y1
e = 2 * dy - dx   # 初始误差
x = x1
y = y1   //显示初始点
for i in range(0, int(dx + 1)):
    plt.plot(x, y, color)
    if e >= 0:   # 如果e >= 0 ，选取右上方的点,y(i+1) = yi + 1,否则y(i+1) = yi
        y ++
        e =e- 2 * dx     #若ei >= 0， e(i+1) = ei +2dy -2dx，否则e(i+1) = ei +2dy
	e =e+ 2 * dy
	x ++
plt.show()

通用：

def BresenhamLine(x1, y1, x2, y2, color):
dx = abs(x2 - x1)
dy = abs(y2 - y1)
sx = 1 if ((x2 - x1) > 0) else -1  #以x为基准的话，如果x要迭代改值的话，则下一步为加1或者减1
sy = 1 if ((y2 - y1) > 0) else -1  #以y为基准的话，如果y要迭代改值的话，则下一步为加1或者减1
boolInterChange = False #根据斜率的大小，交换dx和dy，可以理解为变化x轴和y轴使得斜率的绝对值为[0,1]
if dy > dx:
    np.swapaxes(dx, dy)
    boolInterChange = True #k>1
e = 2 * dy - dx 
x = x1
y = y1 
for i in range(0, int(dx + 1)):
    plt.plot(x, y, color)
    if e >= 0:    #根据斜率的不同，让非基准轴变化一个单位
        if boolInterChange:   #dy更大，斜率>1，则x要+1或者-1
            x += sx
        else:  #dx更大，斜率<1，则y要+1或者-1
            y += sy
            e =e- 2 * dx
        e =e+ 2 * dy
        if boolInterChange:   #根据斜率的不同，让基准轴改变一单位
            y += sy    #k>1,y要改变，如果正向改变，就加一
    else:
        x += sx
plt.show()