基于Python 实现直线段生成算法和圆弧生成算法

基本图形生成算法

直线段

基础算法

计算斜率和截距，通过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.x for xi in range(start.x, end.x): # 栅格的性质 yi = k * xi + b drawPixel(xi, int(yi+0.5), 1, grid) # y坐标要进行近似

数值微分算法(DDA)

• 采用“增量”的思想

• • 当|k|<=1时，x每增加1，y增加k
  • 当|k|>1时，y每增加1，x增加1/k

• 证明:(这里只考虑|k|<=1当情况)
  由

'''数值微分算法（DDA）''' def drawLine_DDA(grid, start, end): k = (end.y - start.y) / (end.x - start.x) xi, yi = start.x, start.y if(abs(k<=1)): for xi in range(start.x, end.x): drawPixel(xi, int(yi+0.5), 1, grid) yi += k else: for yi in range(start.y, end.y): drawPixel(int(xi+0.5), yi, 1, grid) xi += 1/k

如果不对k进行分类讨论

对k进行分类讨论

中点画线法

• 设直线方程为：ax + by + c =0

• • a = y0 - y1
  • b = x1 - x0
  • c = x0y1 - x1y0

• **考核点：**(xp+1, yp+0.5)
• 判别式：

• • 如果 => 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.y xp, yp = start.x, start.y for 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 += 1 else: # yp += 0 pass

在中点画线法中添加增量的思想

• 若取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.x d = a + (b<<2) # 用2d代替d， 摆脱小数 d1, d2 = a<<2, (a+b)<<2 xp, yp = start.x, start.y for xp in range(start.x, end.x): drawPixel(xp, yp, 1, grid) if d<0: yp += 1 d += d2 else: d += d1

Bresenham画线法

• 由误差项符号决定下一个像素选正右方还是右上方
• 判别式：

• • , 取右上(x+1, y+1)
  • else，取正右(x+1, y)

• 引入增量思想：

• • ，增量为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.y e = -0.5 for x in range(start.x, end.x): drawPixel(x, y, 1, grid) if e > 0: e += k - 1 y += 1 else: e += k # y += 0

去点浮

• 用代替
• 去掉k的计算
• 引入增量思想：

• • ，增量为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.y e = -dx for x in range(start.x, end.x): drawPixel(x, y, 1, grid) if e > 0: e += (dy - dx) << 2 y += 1 else: e += (dy) << 2 # y += 0

圆弧

暴力算法

中点画圆法

• 只需画1/8圆（第一象限y>x部分）
• 判别式：

• • F>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 - R x, y = 0, R while x < y: drawPixel_symmetry8(x, y, 1, grid) if d < 0: x += 1 d += 2*x + 3 else: x += 1 y -= 1 d += ((x-y) << 1) + 5

对增量本身再次使用增量思想

• x递增1，d递增
• y递减1，d递增
• 初始值：

'''中点画圆法(DDA)(去点浮)''' def drawArc_MidPoint_with_DDA_nonreal(grid, R): d = 1 - R deltax, deltay = 3, 2 - (R << 1) x, y = 0, R while x < y: drawPixel_symmetry8(x, y, 1, grid) if d < 0: x += 1 d += deltax deltax += 2 else: x += 1 y -= 1 d += (deltax + deltay) deltax += 2 deltay += 2

Bresenham画圆法

• 选取距离真正的圆曲线近的点进行扩展
  
  如果|OP1| > |OP2|，则选P2
  <=>
  <=>
• 当前像素的下一个扩展节点：正右方、右下方、正下方

1. 1. 取H
   2. 在H、D中选更近的
   3. 取D
   4. 在V、D中选更近的
   5. 取V

• 令,
  ,
  
  令
  ,

• • • ，若，取D；else取V
    • ，，取H；else，取D
    • ，取D

• 用增量法简化，下一个像素取：

• • H，增量取2x + 1
  • D，增量取2x - 2y + 2
  • V，增量取-2y + 1
  • 初始值：-2r + 2

'''Bresenham画圆法''' def drawArc_Bresenham(grid, R): delta = (1 - R) << 1 x, y = 0, R while y >= 0: drawPixel_symmetry4(x, y, 1, grid) if delta < 0: delta1 = ((delta + y) << 1) - 1 if delta1 <= 0: direction = 1 else: direction = 2 elif delta > 0: delta2 = ((delta - x) << 1) - 1 if delta2 <= 0: direction = 2 else: direction = 3 else: direction = 2 if direction == 1: # 前进到 正右 x += 1 delta += (x << 1) + 1 elif direction == 2: # 前进到 右下 x += 1 y -= 1 delta += ((x - y) << 1) + 2 else: # 前进到 正下 y -= 1 delta += 1 - (y << 1)

正负法

• 圆方程：
• 设

• • P在圆内 -> -> 向右
  • P在圆外 -> -> 向下

• 引入增量思想：

• • 当F<=0，增量为2x + 1
  • else，增量为-2y + 1
  • 初始值：0

'''正负法''' def drawArc_PositiveNegative(grid, R): F = 0 x, y = 0, R while x <= y: drawPixel_symmetry8(x, y, 1, grid) print(F) if F <= 0: F += (x << 1) + 1 x += 1 else: F += 1 - (y << 1) y -= 1

圆内接正多边形逼近法

• • 工程上，就可以了，两个点的距离达到1pixel之后再小也没用了

• 圆的参数方程:

• 引入增量思想：

'''圆内接正多边形逼近法''' def drawArc_InscribedRegularPolygonApproximate(grid, R): Alpha = 1/R cosAlpha, sinAlpha = cos(Alpha), sin(Alpha) x, y = R, 0 while x >= y: drawPixel_symmetry8(int(x+0.5), int(y+0.5), 1, grid) x = cosAlpha * x - sinAlpha * y y = sinAlpha * x + cosAlpha * y

♻️ 资源

大小：1.49MB

➡️资源下载：https://download.csdn.net/download/s1t16/87404302

注：更多内容可关注微信公众号【神仙别闹】，如当前文章或代码侵犯了您的权益，请私信作者删除！