• 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坐标要进行近似
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    在这里插入图片描述
    在这里插入图片描述


    数值微分算法(DDA)

    • 采用**“增量”**的思想

      • |k|<=1时,x每增加1y增加k
      • |k|>1时,y每增加1x增加1/k
    • 证明: (这里只考虑|k|<=1当情况)

      x i + 1 = x i + 1 x_{i+1} = x_{i} + 1 xi+1=xi+1

      y i + 1 = k ∗ x i + 1 + b = k ∗ ( x i + 1 ) + b = k ∗ x i + b + k = y i + k y_{i+1} = k*x_{i+1} + b = k*(x_{i}+1) + b = k*x_{i} + b + k = y_{i} + k yi+1=kxi+1+b=k(xi+1)+b=kxi+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.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
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    在这里插入图片描述
    在这里插入图片描述

    如果不对k进行分类讨论

    在这里插入图片描述

    不对k进行分类讨论
    ![在这里插入图片描述](https://img-blog.csdnimg.cn/d1bbad90a0874dc3aaa6a9f8e584cfbe.png)
    对k进行分类讨论
    ------

    中点画线法

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

      • a = y0 - y1
      • b = x1 - x0
      • c = x0y1 - x1y0
    • **考核点:**(xp+1, yp+0.5)

    • 判别式: Δ = F ( x p + 1 , y p + 0.5 ) = a ∗ ( x p + 1 ) + b ∗ ( y p + 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.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
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    在这里插入图片描述
    在这里插入图片描述

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

    • 若取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
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    在这里插入图片描述
    在这里插入图片描述


    Bresenham画线法

    • 误差项符号决定下一个像素选正右方还是右上方
    • 判别式: ε = y i + 1 − y i , r − 0.5 \varepsilon = y_{i+1} - y_{i,r} - 0.5 ε=yi+1yi,r0.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.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
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    在这里插入图片描述
    在这里插入图片描述

    去点浮

    • ε ′ = 2 ∗ ε ∗ d x \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.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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    在这里插入图片描述
    在这里插入图片描述


    圆弧

    暴力算法

    • y 2 = R 2 − x 2 y^2 = \sqrt{R^2 - x^2} y2=R2x2

    在这里插入图片描述


    中点画圆法

    • 只需画1/8圆(第一象限 y>x 部分)
    • 判别式: F ( x , y ) = x 2 + y 2 − R 2 F(x,y) = x^2 + y^2 - R^2 F(x,y)=x2+y2R2
      • 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
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    在这里插入图片描述

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

    • x递增1,d递增 Δ x = 2 \Delta x = 2 Δx=2
    • y递减1,d递增 Δ   y = 2 \Delta\ y = 2 Δ y=2
    • 初始值:
      • Δ x = 3 \Delta x = 3 Δx=3
      • Δ   y = − 2 r + 2 \Delta\ y = -2r + 2 Δ y=2r+2
    '''中点画圆法(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
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    在这里插入图片描述


    Bresenham画圆法

    • 选取距离真正的圆曲线近的点进行扩展
      在这里插入图片描述

      如果|OP1| > |OP2|,则选P2

      <=> x 1 2 + y 1 2 − R 2 > R 2 − x 2 2 − y 2 2 \sqrt{x_1^2 + y_1^2 - R^2} > \sqrt{R^2 - x_2^2 - y_2^2} x12+y12R2 >R2x22y22

      <=> x 1 2 + y 1 2 + x 2 2 + y 2 2 − 2 R 2 > 0 x_1^2 + y_1^2 + x_2^2 + y_2^2 - 2R^2 > 0 x12+y12+x22+y222R2>0

    • 当前像素的下一个扩展节点:正右方右下方正下方

    在这里插入图片描述

    1. H
    2. HD中选更近的
    3. D
    4. VD中选更近的
    5. V
    • Δ H = ∣ O H ∣ \Delta H = |OH| ΔH=OH, Δ D = ∣ O D ∣ \Delta D = |OD| ΔD=OD, Δ V = ∣ O V ∣ \Delta V = |OV| ΔV=OV

      δ H D = ∣ Δ H ∣ − ∣ Δ D ∣ = ∣ O H ∣ − ∣ O D ∣ \delta HD = |\Delta H| - |\Delta D| = |OH| - |OD| δHD=∣ΔH∣ΔD=OHOD, δ D V = ∣ Δ D ∣ − ∣ Δ V ∣ \delta DV = |\Delta D| - |\Delta V| δDV=∣ΔD∣ΔV

      1. δ H D = 2 Δ D + 2 y − 1 \delta HD = 2\Delta D + 2y - 1 δHD=D+2y1

      2. δ D V = 2 Δ D − 2 x − 1 \delta DV = 2\Delta D - 2x - 1 δDV=D2x1

        • Δ D > 0 \Delta D > 0 ΔD>0,若 δ D V < = 0 \delta DV <= 0 δDV<=0,取D;else取V
        • Δ D < 0 \Delta D < 0 ΔD<0 δ H D < = 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) << 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)
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    在这里插入图片描述


    正负法

    • 圆方程: F ( x , y ) = x 2 + y 2 − R 2 F(x,y) = x^2 + y^2 - R^2 F(x,y)=x2+y2R2
    • P ( x i , y i ) P(x_i, y_i) P(xi,yi)
      • P在圆内 -> D ( x i , y i ) < = 0 D(x_i,y_i) <= 0 D(xi,yi)<=0 -> 向右
      • P在圆外 -> D ( x i , y i ) > 0 D(x_i,y_i) > 0 D(xi,yi)>0 -> 向下
    • 引入增量思想:
      • 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
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    在这里插入图片描述


    圆内接正多边形逼近法

    • l i m n − > ∞ ( n 边正内接多边形 ) = 圆 lim_{n->\infin}(n边正内接多边形) = 圆 limn>(n边正内接多边形)=

      • 工程上, n − > 2 π R n -> 2\pi R n>2πR就可以了,两个点的距离达到1pixel之后再小也没用了
    • 圆的参数方程:

      • x i = R c o s θ i x_i = Rcos\theta_i xi=Rcosθi
      • y i = R s i n θ i y_i = Rsin\theta_i yi=Rsinθi
    • 引入增量思想:
      ( x i + 1 y i + 1 ) = ( c o s α − s i n α s i n α c o s α ) ( x i y i ) = ( c o s α x i − s i n α y i s i n α x i + c o s α y i ) (

      xi+1yi+1" role="presentation" style="position: relative;">xi+1yi+1
      ) = (
      cosαsinαsinαcosα" role="presentation" style="position: relative;">cosαsinαsinαcosα
      )(
      xiyi" role="presentation" style="position: relative;">xiyi
      ) = (
      cosαxisinαyisinαxi+cosαyi" role="presentation" style="position: relative;">cosαxisinαyisinαxi+cosαyi
      ) (xi+1yi+1)=(cosαsinαsinαcosα)(xiyi)=(cosαxisinαyisinαxi+cosαyi)

    '''圆内接正多边形逼近法'''
    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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    在这里插入图片描述

  • 相关阅读:
    盘点十个让工作效率倍增且有趣的 Python工具包
    去中心化与无平台成员:与 Nasheq.eth、Ivan Manchev和Rob Edwards开启 “智能钱包”系列对话!
    读HDF5格式的文件
    C语言perror
    Python抓取高考网图片
    竞赛选题 深度学习LSTM新冠数据预测
    ik分词器的基本使用
    【Vue2】VantUI项目入门教程
    Object.defineProperty方法(Vue 数据双向绑定原理)
    AI对话系统app开源
  • 原文地址:https://blog.csdn.net/newlw/article/details/125988996