资源下载地址:/download/sheziqiong/86768948
资源下载地址:/download/sheziqiong/86768948
基本图形生成算法
直线段
基础算法
计算斜率和截距,通过y = kx + b
的直线表达式计算每一个x
对应的y
值
'''基础算法'''def drawLine_Basic(grid, start, end):k = (end.y-start.y)/(end.x-start.x)b = start.y - k * start.xfor xi in range(start.x, end.x): # 栅格的性质yi = k * xi + bdrawPixel(xi, int(yi+0.5), 1, grid)# y坐标要进行近似
数值微分算法(DDA)
采用**“增量”**的思想
当|k|<=1
时,x
每增加1
,y
增加k
当|k|>1
时,y
每增加1
,x
增加1/k
证明:(这里只考虑|k|<=1
当情况)
由xi+1=xi+1x_{i+1} = x_{i} + 1xi+1=xi+1
yi+1=k∗xi+1+b=k∗(xi+1)+b=k∗xi+b+k=yi+ky_{i+1} = k*x_{i+1} + b = k*(x_{i}+1) + b = k*x_{i} + b + k = y_{i} + kyi+1=k∗xi+1+b=k∗(xi+1)+b=k∗xi+b+k=yi+k
'''数值微分算法(DDA)'''def drawLine_DDA(grid, start, end):k = (end.y - start.y) / (end.x - start.x)xi, yi = start.x, start.yif(abs(k<=1)):for xi in range(start.x, end.x):drawPixel(xi, int(yi+0.5), 1, grid)yi += kelse:for yi in range(start.y, end.y):drawPixel(int(xi+0.5), yi, 1, grid)xi += 1/k
如果不对k进行分类讨论
不对k进行分类讨论![在这里插入图片描述](https://img-/d1bbad90a0874dc3aaa6a9f8e584cfbe.png)对k进行分类讨论------中点画线法
设直线方程为:ax + by + c =0
a = y0 - y1
b = x1 - x0
c = x0y1 - x1y0
**考核点:**(xp+1, yp+0.5)
判别式:Δ=F(xp+1,yp+0.5)=a∗(xp+1)+b∗(yp+0.5)+c\Delta = F(x_p+1, y_p+0.5) = a*(x_p+1) + b*(y_p+0.5) + cΔ=F(xp+1,yp+0.5)=a∗(xp+1)+b∗(yp+0.5)+c
如果Δ<0\Delta<0Δ<0 => Q点在M下方 => 选p2(x+1, y+1)
else, 选p1(x+1, y)
'''中点画线法(k<=1)'''def drwaLine_MidPoint(grid, start, end):a, b, c = start.y-end.y, end.x-start.x, start.x*end.y-end.x*start.yxp, yp = start.x, start.yfor xp in range(start.x, end.x):drawPixel(xp, yp, 1, grid)delta = a*(xp+1) + b*(yp+0.5) + c # 考核点(xp+1, yp+0.5)if delta<0:yp += 1else:# yp += 0pass
在中点画线法中添加增量的思想
若取p1
,增量为a
若取p2
,增量为a+b
初值:d0 = a + 0.5*b
由于只用d
的符号来判断,可以用2d
代替d
,摆脱浮点数'''中点画线法 with DDA'''def drawLine_MidPoint_with_DDA(grid, start, end):a, b = start.y-end.y, end.x-start.xd = a + (b<<2)# 用2d代替d, 摆脱小数d1, d2 = a<<2, (a+b)<<2xp, yp = start.x, start.yfor xp in range(start.x, end.x):drawPixel(xp, yp, 1, grid)if d<0:yp += 1d += d2else:d += d1
Bresenham画线法
由误差项符号决定下一个像素选正右方还是右上方判别式:ε=yi+1−yi,r−0.5\varepsilon = y_{i+1} - y_{i,r} - 0.5ε=yi+1−yi,r−0.5 ε>0\varepsilon > 0ε>0, 取右上(x+1, y+1)
else,取正右(x+1, y)
引入增量思想:ε>0\varepsilon > 0ε>0,增量为k-1
else,增量为k
初始值:-0.5
'''Bresenham画线法(k<=1)'''def drawLine_Bresenham(grid, start, end):k = (end.y - start.y) / (end.x - start.x)x, y = start.x, start.ye = -0.5for x in range(start.x, end.x):drawPixel(x, y, 1, grid)if e > 0:e += k - 1y += 1else:e += k# y += 0
去点浮
用ε′=2∗ε∗dx\varepsilon' = 2 * \varepsilon * dxε′=2∗ε∗dx代替ε\varepsilonε去掉k
的计算引入增量思想:ε>0\varepsilon > 0ε>0,增量为2(dy - dx)
else,增量为2dy
初始值:-dx
'''Bresenham画线法(去点浮)(k<=1)'''def drawLine_Bresenham_nonreal(grid, start, end):dx, dy = (end.x - start.x), (end.y - start.y)x, y = start.x, start.ye = -dxfor x in range(start.x, end.x):drawPixel(x, y, 1, grid)if e > 0:e += (dy - dx) << 2y += 1else:e += (dy) << 2# y += 0
圆弧
暴力算法
y2=R2−x2y^2 = \sqrt{R^2 - x^2}y2=R2−x2中点画圆法
只需画1/8
圆(第一象限y>x
部分)判别式:F(x,y)=x2+y2−R2F(x,y) = x^2 + y^2 - R^2F(x,y)=x2+y2−R2F>0
,取正右方(x+1, y)
else,取右下方(x+1, y-1)
增量思想:d<0
, 增量为2*x + 3
else, 增量为2*(x-y) + 5
初始值:1.25 - R
**去点浮:**用e = d - 0.25
代替d
初始值:e = 1-R
循环条件:d < 0
<=>e < 0.25
<=e
始终为整数 =>e < 0
'''中点画圆法(DDA)'''def drawArc_MidPoint_with_DDA(grid, R):d = 1 - Rx, y = 0, Rwhile x < y:drawPixel_symmetry8(x, y, 1, grid)if d < 0:x += 1d += 2*x + 3else:x += 1y -= 1d += ((x-y) << 1) + 5
对增量本身再次使用增量思想
x
递增1,d
递增Δx=2\Delta x = 2Δx=2y
递减1,d
递增Δy=2\Delta\ y = 2Δy=2初始值:Δx=3\Delta x = 3Δx=3Δy=−2r+2\Delta\ y = -2r + 2Δy=−2r+2'''中点画圆法(DDA)(去点浮)'''def drawArc_MidPoint_with_DDA_nonreal(grid, R):d = 1 - Rdeltax, deltay = 3, 2 - (R << 1)x, y = 0, Rwhile x < y:drawPixel_symmetry8(x, y, 1, grid)if d < 0:x += 1d += deltaxdeltax += 2else:x += 1y -= 1d += (deltax + deltay)deltax += 2deltay += 2
Bresenham画圆法
选取距离真正的圆曲线近的点进行扩展
如果|OP1| > |OP2|
,则选P2
<=> x12+y12−R2>R2−x22−y22\sqrt{x_1^2 + y_1^2 - R^2} > \sqrt{R^2 - x_2^2 - y_2^2}x12+y12−R2>R2−x22−y22
<=> x12+y12+x22+y22−2R2>0x_1^2 + y_1^2 + x_2^2 + y_2^2 - 2R^2 > 0x12+y12+x22+y22−2R2>0
当前像素的下一个扩展节点:正右方、右下方、正下方
取H
在H
、D
中选更近的取D
在V
、D
中选更近的取V
令ΔH=∣OH∣\Delta H = |OH|ΔH=∣OH∣, ΔD=∣OD∣\Delta D = |OD|ΔD=∣OD∣, ΔV=∣OV∣\Delta V = |OV|ΔV=∣OV∣
令δHD=∣ΔH∣−∣ΔD∣=∣OH∣−∣OD∣\delta HD = |\Delta H| - |\Delta D| = |OH| - |OD|δHD=∣ΔH∣−∣ΔD∣=∣OH∣−∣OD∣, δDV=∣ΔD∣−∣ΔV∣\delta DV = |\Delta D| - |\Delta V|δDV=∣ΔD∣−∣ΔV∣
δHD=2ΔD+2y−1\delta HD = 2\Delta D + 2y - 1δHD=2ΔD+2y−1
δDV=2ΔD−2x−1\delta DV = 2\Delta D - 2x - 1δDV=2ΔD−2x−1
ΔD>0\Delta D > 0ΔD>0,若δDV<=0\delta DV <= 0δDV<=0,取D
;else取V
ΔD<0\Delta D < 0ΔD<0,δHD<=0\delta HD <= 0δHD<=0,取H
;else,取D
ΔD=0\Delta D = 0ΔD=0,取D
用增量法简化ΔD\Delta DΔD,下一个像素取:
H
,增量取2x + 1
D
,增量取2x - 2y + 2
V
,增量取-2y + 1
初始值:-2r + 2
'''Bresenham画圆法'''def drawArc_Bresenham(grid, R):delta = (1 - R) << 1x, y = 0, Rwhile y >= 0:drawPixel_symmetry4(x, y, 1, grid)if delta < 0:delta1 = ((delta + y) << 1) - 1if delta1 <= 0:direction = 1else:direction = 2elif delta > 0:delta2 = ((delta - x) << 1) - 1if delta2 <= 0:direction = 2else:direction = 3else:direction = 2if direction == 1:# 前进到 正右x += 1delta += (x << 1) + 1elif direction == 2: # 前进到 右下x += 1y -= 1delta += ((x - y) << 1) + 2else: # 前进到 正下y -= 1delta += 1 - (y << 1)
正负法
圆方程:F(x,y)=x2+y2−R2F(x,y) = x^2 + y^2 - R^2F(x,y)=x2+y2−R2设P(xi,yi)P(x_i, y_i)P(xi,yi)P
在圆内 -> D(xi,yi)<=0D(x_i,y_i) <= 0D(xi,yi)<=0 -> 向右P
在圆外 -> D(xi,yi)>0D(x_i,y_i) > 0D(xi,yi)>0 -> 向下 引入增量思想:当F<=0
,增量为2x + 1
else,增量为-2y + 1
初始值:0
'''正负法'''def drawArc_PositiveNegative(grid, R):F = 0x, y = 0, Rwhile x <= y:drawPixel_symmetry8(x, y, 1, grid)print(F)if F <= 0:F += (x << 1) + 1x += 1else:F += 1 - (y << 1)y -= 1
圆内接正多边形逼近法
limn−>∞(n边正内接多边形)=圆lim_{n->\infin}(n边正内接多边形) = 圆limn−>∞(n边正内接多边形)=圆
工程上,n−>2πRn -> 2\pi Rn−>2πR就可以了,两个点的距离达到1pixel之后再小也没用了
圆的参数方程:
xi=Rcosθix_i = Rcos\theta_ixi=Rcosθiyi=Rsinθiy_i = Rsin\theta_iyi=Rsinθi
引入增量思想:
(xi+1yi+1)=(cosα−sinαsinαcosα)(xiyi)=(cosαxi−sinαyisinαxi+cosαyi)(\begin{matrix}x_{i+1} \\ y_{i+1} \end{matrix}) = (\begin{matrix}cos\alpha & -sin\alpha \\ sin\alpha & cos\alpha \end{matrix})(\begin{matrix}x_{i} \\ y_{i} \end{matrix}) = (\begin{matrix}cos\alpha x_i - sin\alpha y_i \\ sin\alpha x_i + cos\alpha y_i \end{matrix}) (xi+1yi+1)=(cosαsinα−sinαcosα)(xiyi)=(cosαxi−sinαyisinαxi+cosαyi)
'''圆内接正多边形逼近法'''def drawArc_InscribedRegularPolygonApproximate(grid, R):Alpha = 1/RcosAlpha, sinAlpha = cos(Alpha), sin(Alpha)x, y = R, 0while x >= y:drawPixel_symmetry8(int(x+0.5), int(y+0.5), 1, grid)x = cosAlpha * x - sinAlpha * yy = sinAlpha * x + cosAlpha * y
资源下载地址:/download/sheziqiong/86768948
资源下载地址:/download/sheziqiong/86768948