Bresenham算法画直线

本博客仅限于斜率在0~1之间的直线

原算法

设直线起始点坐标为(xs,ys),均为整数，即
x1 = xs, y1 = ys
e(x2) = y2 - y1 - 0.5 = m - 0.5
终点坐标为（xe,ye）
dx = xe-xs,dy = ye-ys;

m = (double)dy/(double)dx;
e = m-0.5;
for(int i = 0;i<dx;i++){
    gl_Point(x,y);
    if(e>=0){
        y = y+1;e=e-1;
    }
    x = x+1;e=e+m;

为了去掉算法中的除法，提高算法的效率和减少算法的复杂性，可以令f = 2*e*dx;

f = 2 * dy - dx;
for (int i = 0; i<dx; i++) { gl_Point(x,y); if (f >= 0) { y = y + 1; f = f - 2*dx; }
    x = x + 1;
    f = f + 2 * dy;
}

用openGL实现如下：

#include<iostream>
#include "gl\glut.h"
using namespace std;

int xx, yy, x2, y2;
void bresenham(int xs, int ys, int xe, int ye);
void lineSegment()
{
    glClear(GL_COLOR_BUFFER_BIT);
    glColor3f(1.0, 0.0, 0.0);//设置点的颜色为红色
    glBegin(GL_POINTS);
    bresenham(xx, yy, x2, y2);
    glEnd();
    glFlush();//必须得加
}

void bresenham(int xs, int ys, int xe, int ye) {
    int x = xs, y = ys, dx, dy;
    dx = xe - xs;
    dy = ye - ys;
    int f = 2 * dy - dx;
    for (int i = 0; i<dx; i++) {
        glVertex2d(x, y);
        if (f >= 0) {
            printf("f=%d>=0 ", f);
        }
        else {
            printf("f=%d<0 ", f);
        }
        if (f >= 0) {
            y = y + 1;
            f = f - 2*dx;
        }
        x = x + 1;
        f = f + 2 * dy;
        printf("(%d,%d)\n", x, y);
    }
}

int main(int argc, char * argv[]) {
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
    printf("输入起始坐标和终点坐标:\n");
    scanf("%d,%d,%d,%d", &xx, &yy, &x2, &y2);
    glutInitWindowPosition(50, 100);
    glutInitWindowSize(500, 500);
    glutCreateWindow("Bresenham画线算法");
    glClearColor(0.0, 0.0, 0.0, 0.0);//设置背景为黑色
    glMatrixMode(GL_PROJECTION);
    gluOrtho2D(0.0, 500.0, 0.0, 500.0);
    glutDisplayFunc(lineSegment);
    glutMainLoop();

}

输入1，1，400，300结果如下：