布雷森汉线算法中追踪所有 8 个八度音阶的图解

原文:https://www . geeksforgeeks . org/illustration-for-tracing-all-the-the-8-octaves-in-bresenhams-line-algorithm/

先决条件: 布雷森汉姆线生成算法

在本文中，我们将了解如何使用布雷森汉的直线算法来寻找所有的八度音阶。

在理解算法的同时只考虑两点 P 0 (x 0 、y 0 ) 和 P 1 (x 1 、y 1 ) 的坐标使得x0<x1和 y 任务是在像素的电脑屏幕上找到画线所需的所有中间点 P 0 (x 0 、y 0 ) 和 P 1 (x 1 、y 1 ) 。

下面是 Bresenham 的直线算法中使用的算法:

plotLine(x0, y0, x1, y1)
    dx = x1 - x0
    dy = y1 - y0
    D = 2*dy - dx
    DE = 2*dy
    DNE = 2(dy - dx)
    y = y0
    x = x0
    plot(x, y)
    while (x < x1)
        if D > 0
            D = D + DNE
            y = y + 1
        else
               D = D + DE
        end if
        x = x + 1
        plot(x, y)
    end while

以下是在其他八度音阶中画线时应该做的改变:

  • 八度 1: 无。
  • 八度 2: 切换 x 和 y 的角色。
  • 八度 3: 切换 x 和 y 的角色；使用规则(8)。
  • 八度 4: 从 P1 画到 P0；使用规则(8)。
  • 八度 5: 从 P1 画到 P0。
  • 八度 6: 从 P1 画到 P0；使用规则(2)。
  • 八度 7: 切换 x 和 y 的角色；使用规则(4)。
  • 八度音程 8: 使用 y = y–1。

下图为第一个八度音:

P0 =(5.8)和 P1 =(9.11)【dx = x1–x0 = 9–5 = 4 dy = y1–y0 = 11–8 = 3 d = 2 * dy–dx = 2(3)-4 = 2 de = 2 * dy = 2 * 3 = 6 dne = 2(dy–dx)= 2(3–4)

最初，绘制 (x 0 ，y 0 ) ，即 (5，8)

  • 图(5，8)
  • D = 2 ->选择 NE->绘制(6，9)-> D = 2+DNE = 2–2 = 0。
  • D = 0 -> E 被选中->绘制(7，9) -> D = 2 + DE = 0 + 6 = 6。
  • D = 6 ->选择 NE->绘制(8，10)-> D = 6+DNE = 6–2 = 4。
  • D = 4 ->选择 NE->绘制(9，11)-> D = 4+DNE = 4–2 = 2。
  • x = x1，因此在循环时退出。

标绘的点是(5，8)、(6，9)、(7，9)、(8，10)、(9，11)。

下图为第二个八度音:

P0 = (2，6)和 P1 = (5，15)

= >对第三个八度音执行以下步骤:

  • 交换 x 和 y 的角色意味着交换(x0，y0)和交换(x1，y1)，在绘图时，我们必须绘制(y，x)
  • 新的点变成 P0 = (6，2)和 P1 = (15，5)

dx = x1–x0 = 15–6 = 9 dy = y1–y0 = 5–2 = 3 d = 2 * dy–dx = 2(3)-9 = 6–9 =-3 de = 2 * dy = 2 * 3 = 6 dne = 2(dy–dx)= 2(3–9)= = 12

首先，我们要绘制 (y 0 ，x 0 ) ，也就是 (2，6)

  • 图(2，6)。
  • D = -3 ->选择 E->绘制(2，7) -> D = -3 + DE = -3 + 6 = 3。
  • D = 3 ->选择 NE->绘制(3，8)。-> D = 3 + DNE = 3 + -12 = -9。
  • D = -9 -> E 被选中->绘制(3，9) -> D = -9 + DE = -9 + 6 = -3。
  • D = -3 ->选择 E->绘制(3，10) -> D = -3 + DE = -3 + 6 = 3。
  • D = 3 ->选择 NE->绘制(4，11)。-> D = 3 + DNE = 3 + -12 = -9。
  • D = -9 -> E 被选中->绘制(4，12) -> D = -9 + DE = -9 + 6 = -3。
  • D = -3 ->选择 E->绘制(4，13) -> D = -3 + DE = -3 + 6 = 3。
  • D = 3 ->选择 NE->绘图(5，14)。-> D = 3 + DNE = 3 + -12 = -9。
  • D = -9 -> E 被选中->绘制(5，15) -> D = -9 + DE = -9 + 6 = -3。
  • x = x1，因此在循环时退出。

标绘的点为(2，6)、(2，7)、(3，8)、(3，9)、(3，10)、(4，11)、(4，12)、(4，13)、(5，14)、(5，15)。

下图为第三个八度音:

P0 = (-2，4)和 P1 = (-6，12)

对第三个八度音执行以下步骤:

  • 交换 x 和 y =交换(x0，y0)和交换(x1，y1)的角色，在绘图时，我们必须绘制(y，x)
  • 使用 y = y–1 =我们必须使用 y = y–1，而不是 y = y + 1 和 dy = -dy。
  • 新的点变成 P0 = (4，-2)和 P1 = (12，-6)

dx = x1–0x 0 = 12–4 = 8 dy = y1–y0 =-6–(-2)= 4

我们得让 dy = -dy。因此，dy = +4

d = 2 * dy–dx = 2(4)–8–8 = 0 de = 2 * dy = 2 * 4 = 8 dne = 2(dy–dx)= 2(4–8)= = 8

最初，我们要绘制(y 0 ，x 0 )也就是(-2，4)

  • 图(-2，4)。
  • D = 0 -> E 被选中->绘图(-2，5) -> D = 0 + DE = 0 + 8 = 8。
  • D = 8 ->选择 NE->绘制(-3，6)。-> D = 8 + DNE = 8 + -8 = 0。
  • D = 0 -> E 被选中->绘图(-3，7) -> D = 0 + DE = 0 + 8 = 8。
  • D = 8 ->选择 NE->绘制(-4，8)。-> D = 8 + DNE = 8 + -8 = 0。
  • D = 0 -> E 被选中->绘图(-4，9) -> D = 0 + DE = 0 + 8 = 8。
  • D = 8 ->选择 NE->绘图(-5，10)。-> D = 8 + DNE = 8 + -8 = 0。
  • D = 0 -> E 被选中->绘图(-5，11) -> D = 0 + DE = 0 + 8 = 8。
  • D = 8 ->选择 NE->绘图(-6，12)。-> D = 8 + DNE = 8 + -8 = 0。
  • x = x1，因此在循环时退出。

标绘的点是(-2，4)、(-2，5)、(-3，6)、(-3，7)、(-4，8)、(-4，9)、(-5，10)、(-5，11)、(-6，12)。

下图为第四个八度音:

P0 = (-2，1)和 P1 = (-6，3)

对第四个八度音执行以下步骤:

  • 从 P1 抽签到 P0 =交换(P0，P1)。
  • 使用 y = y–1 =我们必须使用 y = y–1，而不是 y = y + 1 和 dy = -dy。
  • 新的点变成 P0 = (-6，3)和 P1 = (-2，1) */

dx = x1–x0 =-2-(-6)= 4 dy = y1–y0 = 1–3 =-2

我们得让 dy = -dy。因此，dy = +2

d = 2 * dy–dx = 2(2)–4–4 = 0 de = 2 * dy = 2 * 2 = 4 dne = 2(dy–dx)= 2(2–4)= = 4

首先，我们要画出(x0，y0)，它是(-6，3)

  • 图(-6，3)。
  • D = 0 -> E 被选中->绘图(-5，3) -> D = 0 + DE = 0 + 4 = 4。
  • D = 4 ->选择 NE->绘制(-4，2)。-> D = 4 + DNE = 4 + -4 = 0。
  • D = 0 -> E 被选中->绘图(-3，2) -> D = 0 + DE = 0 + 4 = 4。
  • D = 4 ->选择 NE->绘制(-2，1)。-> D = 4 + DNE = 4 + -4 = 0。
  • x = x1，因此在循环时退出。

绘制的点是(-6，3)、(-5，3)、(-4，2)、(-3，2)、(-2，1)。

下图为第五个八度音:

P0 = (-3，-1)和 P1 = (-9，-3)

对第五个八度音执行以下步骤:

  • 从 P1 抽签到 P0 =交换(P0，P1)。
  • 新的点变成 P0 = (-9，-3)和 P1 = (-3，-1)

dx = x1–x0 =-3-(-9)= 6 dy = y1–y0 =-1-(-3)= 2 d = 2 * dy–dx = 2(2)–6 = 4–6 =-2 de = 2 * dy = 2 * 2 = 4 dne = 2(dy–dx)= 2(2–6)= = 8

首先，我们必须绘制(x0，y0)图，它是(-9，-3)

  • 图(-9，-3)。
  • D = -2 -> E 被选中->绘图(-8，-3) -> D = -2 + DE = -2 + 4 = 2。
  • D = 2 ->选择 NE->绘制(-7，-2)。-> D = 2 + DNE = 2 + -8 = -6。
  • D = -6 -> E 被选中->绘图(-6，-2) -> D = -6 + DE = -6 + 4 = -2。
  • D = -2 -> E 被选中->绘图(-5，-2) -> D = -2 + DE = -2 + 4 = 2。
  • D = 2 ->选择 NE->绘制(-4，-1)。-> D = 2 + DNE = 2 + -8 = -6。
  • D = -6 -> E 被选中->绘图(-3，-1) -> D = -6 + DE = -6 + 4 = -2。
  • x = x1，因此在循环时退出。

绘制的点是(-9，-3)、(-8，-3)、(-7，-2)、(-6，-2)、(-5，-2)、(-4，-1)、(-3，-1)。

下图为第六个八度音:

P0 = (-1，-2)和 P1 = (-3，-6)

对第六个八度音执行以下步骤:

  • 从 P1 抽签到 P0 =交换(P0，P1)。
  • 交换 x 和 y =交换(x0，y0)和交换(x1，y1)的角色，在绘图时，我们必须绘制(y，x)。
  • 新的点变成 P0 = (-6，-3)和 P1 = (-2，-1)

dx = x1–0x 0 =-2-(-6)= 4 dy = y1–y0 =-1-(-3)= 2 d = 2 * dy–dx = 2(2)–4–4 = 0 de = 2 * dy = 2 * 2 = 4 dne = 2(dy–dx)= 2(2–4)= = 4

最初，我们必须绘制(y0，x0)图，它是(-3，-6)

  • 图(-3，-6)。
  • D = 0 -> E 被选中->绘图(-3，-5) -> D = 0 + DE = 0 + 4 = 4。
  • D = 4 ->选择 NE->绘制(-2，-4)。-> D = 4 + DNE = 4 + -4 = 0。
  • D = 0 -> E 被选中->绘图(-2，-3) -> D = 0 + DE = 0 + 4 = 4。
  • D = 4 ->选择 NE->绘制(-1，-2)。-> D = 4 + DNE = 4 + -4 = 0。
  • x = x1，因此在循环时退出。

绘制的点是(-3，-6)、(-3，-5)、(-2，-4)、(-2，-3)、(-1，-2)。

下图为第七个八度音:

P0 = (2，-5)和 P1 = (4，-10)

对第七个八度音执行以下步骤:

  • 交换 x 和 y =交换(x0，y0)和交换(x1，y1)的角色，在绘图时，我们必须绘制(y，x)。
  • 从 P1 抽签到 P0 =交换(P0，P1)。
  • 使用 y = y–1 =我们必须使用 y = y–1，而不是 y = y + 1 和 dy = -dy。
  • 新的点变成 P0 = (-10，4)和 P1 = (-5，2)

dx = x1–x0 =-5-(-10)= 5 dy = y1–y0 = 2–4 =-2

我们得让 dy = -dy。因此，dy = +2

d = 2 * dy–dx = 2(2)–5 = 4–5 =-1 de = 2 * dy = 2(2)= 4 dne = 2(dy–dx)= 2(2–5)= 6

最初，我们必须绘制(y0，x0)图，它是(4，-10)

  • 图(4，-10)。
  • D = -1 ->选择 E->绘制(4，-9) -> D = -1 + DE = -1 + 4 = 3。
  • D = 3 ->选择 NE->绘制(3，-8)。-> D = 3 + DNE = 3 + -6 = -3。
  • D = -3 -> E 被选中->绘制(3，-7) -> D = -3 + DE = -3 + 4 = 1。
  • D = 1 ->选择 NE->绘制(2，-6)。-> D = 1 + DNE = 1 + -6 = -5。
  • D = -5 ->选择 E->绘制(2，-5) -> D = -5 + DE = -5 + 4 = -1。
  • x = x1，因此在循环时退出。

绘制的点是(-4，10)、(-4，9)、(-3，8)、(-3，7)、(-2，6)、(-2，5)。

下图为第八个八度音:

P0 = (3，-2)和 P1 = (6，-4)

对第八个八度音执行以下步骤:

  • 使用 y = y–1 =我们必须使用 y = y–1，而不是 y = y + 1 和 dy = -dy。

dx = x1–x0 = 6–3 = 3 dy = y1–y0 =-4–(-2)= 2

我们得让 dy = -dy。因此，dy = +2

d = 2 * dy–dx = 2(2)–3 = 4–3 = 1 de = 2 * dy = 2 * 2 = 4 dne = 2(dy–dx)= 2(2–3)= = 2

最初，我们必须绘制(x 0 ，y0)，即(3，-2)

  • 图(3，-2)。
  • D = 1 ->选择 NE->绘制(4，-3) -> D = 1 + DNE = 1 + (-2) = -1。
  • D = -1 ->选择 E->绘制(5，-3)。-> D = -1 + DE = -1 + 4 = 3。
  • D = 3 ->选择 NE->绘制(6，-4) -> D = 3 + DNE = 3 + -2 = 1。
  • x = x1，因此在循环时退出。

绘制的点是(3，-2)，(4，-3)，(5，-3)，(6，-4)。

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://moonapi.com/news/35462.html