计算机图形学_bresenham画线算法的最简洁实现(已验证)

青旅半醒 2022-09-02 13:47 169阅读 0赞

**目录**

1. 说明

2. 实现

3. 完整测试代码

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

# 1. 说明 #

具体的bresenham算法可以参考https://www.cs.helsinki.fi/group/goa/mallinnus/lines/bresenh.html，这里介绍的是一种基于该算法的实现方式。为什么说是最简洁的实现的看下面的代码实现就知道了，短短不到三十行代码便可以实现全坐标系**任意斜率直线**的绘制。

这里采用了**虚拟轴**的概念，因而使得可以屏蔽斜率的概念可以使得所有的直线绘制都转化为第一象限斜率小于1情况下的直线绘制。因此所有的判定条件只有一个e+dy-0.5dx

# 2. 实现 #

std::vector<Point> bresenham(Point start_point, Point end_point) {
        std::vector <Point> res;
        Point pos = start_point;
        int direction_x = end_point.x - start_point.x;
        int direction_y = end_point.y - start_point.y;
        int delta_x = fabs(direction_x);
        int delta_y = fabs(direction_y);
        int max_xy = ((delta_x > delta_y) ? delta_x : delta_y);
        int decision_param_x = - (max_xy / 2);
        int decision_param_y = decision_param_x;
    
        res.push_back(start_point);
        for(int i = 0; i < max_xy; ++i) {
            //处理x
            decision_param_x += delta_x;
            if(decision_param_x > 0) {
                direction_x > 0 ? pos.x++ : pos.x--;
                decision_param_x -= max_xy;
            }
            //处理y
            decision_param_y += delta_y;
            if(decision_param_y > 0) {
                direction_y > 0 ? pos.y++ : pos.y--;
                decision_param_y -= max_xy;
            }
            res.push_back(pos);
        }
        return res;
    }

以上便是该算法实现的全部内容，可以很容易移植到不同的测试环境中测试。下图是在windows平台终端下的测试结果。  
![\[(img-ESZ2X1O3-1570684984231)(C:\\Users\\xiaoyuan\\AppData\\Roaming\\Typora\\typora-user-images\\1570684307116.png)\]][img-ESZ2X1O3-1570684984231_C_Users_xiaoyuan_AppData_Roaming_Typora_typora-user-images_1570684307116.png]

# 3. 完整测试代码 #

以下为完整的测试代码：

#include <iostream>
    #include <windows.h>
    #include <vector>
    #include <cmath>
    
    typedef struct 
    {
        int x;
        int y;
    }Point;
    
    Point start_point = {15, 15};
    Point end_point = {8, 0};
    
    
    std::vector<Point> bresenham(Point start_point, Point end_point) {
        std::vector <Point> res;
        Point pos = start_point;
        int direction_x = end_point.x - start_point.x;
        int direction_y = end_point.y - start_point.y;
        int delta_x = fabs(direction_x);
        int delta_y = fabs(direction_y);
        int max_xy = ((delta_x > delta_y) ? delta_x : delta_y);
        int decision_param_x = - (max_xy / 2);
        int decision_param_y = decision_param_x;
    
        res.push_back(start_point);
        for(int i = 0; i < max_xy; ++i) {
            //处理x
            decision_param_x += delta_x;
            if(decision_param_x > 0) {
                direction_x > 0 ? pos.x++ : pos.x--;
                decision_param_x -= max_xy;
            }
            //处理y
            decision_param_y += delta_y;
            if(decision_param_y > 0) {
                direction_y > 0 ? pos.y++ : pos.y--;
                decision_param_y -= max_xy;
            }
            res.push_back(pos);
        }
        return res;
    }
    
    void gotoXY(int x, int y)
    {
        COORD cd;    
    	cd.X   =   x; 
    	cd.Y   =   y;     
    	SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),cd); 
    }
    
    int main(void)
    {
        std::vector<Point> point_set = bresenham(start_point, end_point);
        system("cls");
        for(int i = 0; i < point_set.size(); ++i)
        {
            gotoXY(point_set[i].x, point_set[i].y);
            std::cout << "*" ; 
        }
        gotoXY(0,30);
    }

[img-ESZ2X1O3-1570684984231_C_Users_xiaoyuan_AppData_Roaming_Typora_typora-user-images_1570684307116.png]: /images/20220829/ab76dd277bcf4a6b91ef28eff160ddf1.png