【计算机图形学|直线生成算法】中点画线法-Toy模板网

这篇具有很好参考价值的文章主要介绍了【计算机图形学|直线生成算法】中点画线法。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

概述

中点画线法（Midpoint Line Algorithm）是一种画线（Line Drawing）算法，用来在计算机屏幕上绘制线条。

它的基本思想是从线段的起点和终点出发，按照一定的规则向终点逐步逼近，并在途中以控制变量的方式得出每个像素点的坐标，从而绘制出所需的线条。

具体实现中，中点画线法通过计算线段斜率的变化情况，来分为斜率小于1和大于等于1两种情况，并采用Bresenham的对称性原理，以中点的颜色来控制每个像素点的生长方向，从而获得较高的绘制效率和图像质量表现。

总的来说，中点画线法是一种高效且易于实现的线段绘制算法，也是计算机图形学领域最基本的算法之一。

一、基本思想

当前像素点为 $x_p,y_p)$ ，下一个像素点为 $P 1$ 或 $P 2$ 。
设 $M=(x_p+1,y_p+0.5)$ 为 $P 1$ 与 $P 2$ 之中点， $Q$ 为理想直线与 $x=x_p+1$ 垂线的交点。将 $Q$ 与 $M$ 的 $y$ 坐标进行比较。
当 $M$ 在 $Q$ 的下方，则 $P 2$ 应为下一个像素点；当 $M$ 在 $Q$ 的上方，则 $P 1$ 应为下一个像素点。
中点画线法,计算机图形学,算法

二、构造判别式:

$d=F(M)=F(x_p+1,y_p+0.5)=a(x_p+1)+b(y_p+0.5)+c$
其中， $a=y_0-y_1, b=x_1-x_0, c=x_0y_1-x_1y_0$ .

当 $d < 0$ 时， $M$ 在 $L (Q$ 点 $)$ 下方，取右上方 $P2(x_p+1,y_p+1)$ 为下一个像素；
当 $d > 0$ 时， $M$ 在 $L (Q$ 点 $)$ 上方，取右方 $P1(x_p+1,y_p)$ 为下一个像素；
当 $d = 0$ 时，选 $P 1$ 或 $P 2$ 均可，约定取 $P1(x_p+1,y_p)$ 为下一个像素；

三、递推出增量

若当前像素处于：

$d\geq 0$ 情况，则取正右方像素 $P1(x_p+1, y_p)$ ，要判下一个像素位置，应计算
$d1=F(x_p+2, y_p+0.5)=a(x_p+2)+b(y_p+0.5)=d+a$
增量为 $a$ 。

$d < 0$ 时，则取右上方像素 $P2(x_p+1, y_p+1)$ 。要判断再下一像素，则要计算
$d2= F(x_p+2, y_p+1.5)=a(x_p+2)+b(y_p+1.5)+c=d+a+b$
增量为 $a + b$ 。

优化：

由于画线从 $x_0, y_0$ )开始， $d$ 的初值为：
$d_0=F(x_0+1, y_0+0.5)=F(x_0, y_0)+a+0.5b=a+0.5b$
可以用 $2 d$ 代替 $d$ 来避免小数，提高效率。令 $d_0=2a+b, d_1=2a, d_2=2a+2b$ 。

总结：

如果 $d > 0$ ，则中点 $x_, y_m)$ 在 $L (Q)$ 的上方，此时应该取右边的像素点 $P1(x_p+1,y_p)$ ，即 $x$ 加1、 $y$ 不变。此时， $d$ 的值增加 $d 1$ ，即 $d = d + d 1$ 。

如果 $d < 0$ ，则中点 $x_m, y_m)$ 在 $L (Q)$ 的下方，应该取右上方的像素点 $P2(x_p+1,y_p+1)$ ，即 $x$ 和 $y$ 均加1。此时， $d$ 的值增加 $d 2$ ，即 $d = d + d 2$ 。

四、例题分析

以P0（0,0）到P1（5,2）为例，使用中点画线法，计算 $d_0$ ， $d_1$ 和 $d_2$ ，并画出对应表格。

首先，根据两点坐标求出 $a$ 、 $b$ 、 $c$ 的值，有：
$a=y_0-y_1=-2$
$b=x_1-x_0=5$
$c=x_0y_1-x_1y_0=-10$

接着，根据公式得到 $d_0$ ， $d_1$ 和 $d_2$ 的初值，有：
$d_0 = 2a+b = 1$
$d_1 = 2a = -4$
$d_2 = 2a+2b = 6$

然后，根据中点画线法的算法流程结合总结，可以按照如下表格计算每个像素点的坐标 $x_i,y_i)$ 以及 $d_i$ 的变化：

count	x	y	d	P
0	0	0	1	P0
1	1	0	-3
2	2	1	3
3	3	1	-1
4	4	2	5
5	5	2	1	P1

其中， $P$ 表示像素点位置， $co u n t$ 表示计数， $d$ 表示中点到直线距离的判别式值（经过放大2倍），根据 $d > 0$ 还是 $d < 0$ 判断所选的下一个像素点。对于 $d = 0$ ，约定选择右下方的像素点。

最终，依照算法，连线的轨迹如下：

P0 (0, 0) -> (1, 1) -> (2, 1) -> (3, 2) -> (4, 2) -> P1 (5, 2)

如下图：
中点画线法,计算机图形学,算法文章来源地址https://www.toymoban.com/news/detail-762918.html

五、伪代码

/* mid PointLine */
void Midpoint Line (int x0,int y0,int x1, int y1,int color)
     {   int a, b, d1, d2, d, x, y;
    a=y0-y1, b=x1-x0, d=2*a+b;
    d1=2*a, d2=2* (a+b);
    x=x0, y=y0;
    drawpixel(x, y, color);
    while (x<x1)
    { if (d<0)       {x++, y++, d+=d2; }
     else       {x++, d+=d1;}
     drawpixel (x, y, color);
     }  /* while */
 }