直线绘制算法

﹏ヽ暗。殇╰゛Y 2022-03-26 05:24 390阅读 0赞

**目录**

*  数值微分法
 *  中点画线法
 *  Bresenham算法

--------------------

三种常用直线绘制算法：

1）数值微分法（Digital Differential Analyzer，DDA）

2）中点画线法

3）Bresenham算法

## 数值微分法 ##

1. 应用直线公式：F(x) = y = kx+b

2. 条件：

1> 斜率的绝对值 |k| <= 1。当|k| > 1时，交换x和y的位置，即公式变为：x = y/k + (-b/k)

【为什么要求 |k| <= 1 ？这是为了保证x+1，y只可能+0或+1，而不会+2，继而造成直线的部分缺失】

2> y和k为float型，且每一次运算后需要对y取整

3. 计算像素点：x+1，y+k（取整）

4. 代码：

void DDALine(int x0, int y0, int x1, int y1, int color) 
    {
        int x;                 /*像素点的x轴坐标*/
    
        float dx, dy, y, k;    /*x与y的增量分别为dx和dy，y为y轴坐标，k为斜率*/
    
        dx = x1 - x0, dy = y1 - y0;    /*计算增量*/
    
        k = dy / dx;           /*计算斜率*/
    
        y = y0;                /*给y赋初值*/
    
        for (x = x0; x < x1; x++)    /*给x赋初值，并逐步向x1移动*/
        {
            drawpixel(x, int(y+0.5), color);    /*给y取整，画像素点*/
            
            y=y+k;        /*y+k，x+1*/
        }
    }

5. 缺点：对y的取整操作对硬件不友好。

## 中点画线法 ##

1. 应用直线公式：F(x,y) = a\*x + b\*y + c = 0

2. 条件：斜率的绝对值 |-a/b| <= 1

3. 计算：

1> 初始判别式 d0 = 2a + b

2> 根据判别式d的正负，求出新的y和d：d >= 0，y不变，d = d + 2a；d < 0，y + 1，d = d + 2a + 2b

4. 例题：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hhMWZfQXdha2U_size_16_color_FFFFFF_t_70][]

## Bresenham算法 ##

1. 计算：

1> dy = y1 - y0; dx = x1 - x0

2> 初始判别式 d0 = 2dy - dx

3> 根据判别式d的正负，求出新的y和d：d >= 0，y + 1，d = d + 2(dy - dx)；d < 0，y不变，d = d + 2dy

2. 例题：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hhMWZfQXdha2U_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hhMWZfQXdha2U_size_16_color_FFFFFF_t_70]: /images/20220326/812d0863570642089dbc983f72382b85.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0hhMWZfQXdha2U_size_16_color_FFFFFF_t_70 1]: /images/20220326/3ff421166865401c905639bc3aff7470.png