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当情况)

  由 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​=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.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进行分类讨论  对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

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

• 若取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画线法

• 由误差项符号决定下一个像素选正右方还是右上方
• 判别式： ε = y i + 1 − y i , 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.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

去点浮

• 用 ε ′ = 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

---

圆弧 暴力算法

• y 2 = R 2 − x 2 y^2 = sqrt{R^2 - x^2} y2=R2−x2 ​

---

中点画圆法

• 只需画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+y2−R2
  • 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递增 Δ 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

---

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​+y12​−R2 ​>R2−x22​−y22​ ​

  <=> 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​+y22​−2R2>0

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

1. 取H
2. 在H、D中选更近的
3. 取D
4. 在V、D中选更近的
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∣=∣OH∣−∣OD∣, δ D V = ∣ Δ D ∣ − ∣ Δ V ∣ delta DV = |Delta D| - |Delta V| δDV=∣ΔD∣−∣ΔV∣

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

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

     • Δ 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)

---

正负法

• 圆方程： F ( x , y ) = x 2 + y 2 − R 2 F(x,y) = x^2 + y^2 - R^2 F(x,y)=x2+y2−R2
• 设 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

---

圆内接正多边形逼近法

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

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

• 圆的参数方程:

  • x i = R c o s θ i x_i = Rcostheta_i xi​=Rcosθi​
  • y i = R s i n θ i y_i = Rsintheta_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 ) (begin{matrix}x_{i+1} \ y_{i+1} end{matrix}) = (begin{matrix}cosalpha & -sinalpha \ sinalpha & cosalpha end{matrix})(begin{matrix}x_{i} \ y_{i} end{matrix}) = (begin{matrix}cosalpha x_i - sinalpha y_i \ sinalpha x_i + cosalpha y_i end{matrix}) (xi+1​yi+1​​)=(cosαsinα​−sinαcosα​)(xi​yi​​)=(cosαxi​−sinαyi​sinα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