每日算法 — 使用java实现Bresenham直线算法：整数运算优化像素级直线绘制

Bresenham直线算法是计算机图形学中的经典算法，由Jack Elton Bresenham于1962年在IBM提出。该算法的核心思想是利用整数运算和增量计算，在光栅显示器上高效地绘制近似直线的像素点集。相比直接使用浮点运算计算直线上的每个点，Bresenham算法完全避免了耗时的浮点乘除法，仅通过整数加减法和位运算即可完成绘制，在早期硬件资源有限的计算机上具有巨大的性能优势。

算法原理

在二维光栅网格中，给定起点 $(x_0, y_0)$ 和终点 $(x_1, y_1)$，目标是确定一组最逼近理想直线的整数坐标像素点。Bresenham算法的关键在于引入一个决策参数（decision parameter），通过该参数的符号来判断下一个像素点应该选择右侧点还是右上侧点（假设斜率在0到1之间）。

对于斜率 $0 < m < 1$ 的直线，算法维护一个误差项 $d$。初始时，$d = 2\Delta y – \Delta x$。在每一步：
– 若 $d < 0$，选择右侧像素点，并更新 $d = d + 2\Delta y$
– 若 $d \geq 0$，选择右上侧像素点，并更新 $d = d + 2\Delta y – 2\Delta x$

这一增量更新策略使得算法每步仅需两次整数加法和一次比较操作，时间复杂度为 $O(\Delta x)$，空间复杂度为 $O(1)$。

Java实现

以下代码实现了通用版本的Bresenham直线算法，支持任意斜率的直线绘制，并扩展支持反走样渲染。

import java.awt.image.BufferedImage;
import java.awt.Color;

/**
 * Bresenham直线算法实现
 * 支持任意斜率的直线绘制，以及基础反走样（Wu反走样）
 */
public class BresenhamLine {

    /**
     * 经典Bresenham直线绘制算法
     * @param image 目标图像
     * @param x0 起点x坐标
     * @param y0 起点y坐标
     * @param x1 终点x坐标
     * @param y1 终点y坐标
     * @param color 线条颜色
     */
    public static void drawLine(BufferedImage image, int x0, int y0, int x1, int y1, Color color) {
        int dx = Math.abs(x1 - x0);
        int dy = Math.abs(y1 - y0);

        // 确定步进方向
        int sx = x0 < x1 ? 1 : -1;
        int sy = y0 < y1 ? 1 : -1;

        // 初始误差项
        int err = dx - dy;

        while (true) {
            // 绘制当前像素
            if (x0 >= 0 && x0 < image.getWidth() && y0 >= 0 && y0 < image.getHeight()) {
                image.setRGB(x0, y0, color.getRGB());
            }

            // 到达终点则退出
            if (x0 == x1 && y0 == y1) break;

            int e2 = 2 * err;

            // 根据误差项决定下一步进方向
            if (e2 > -dy) {
                err -= dy;
                x0 += sx;
            }
            if (e2 < dx) {
                err += dx;
                y0 += sy;
            }
        }
    }

    /**
     * 中点画线算法（Bresenham的等价形式）
     * 适用于斜率0到1之间的直线
     */
    public static void drawLineMidpoint(BufferedImage image, int x0, int y0, int x1, int y1, Color color) {
        int dx = x1 - x0;
        int dy = y1 - y0;
        int d = 2 * dy - dx;      // 初始决策参数
        int incrE = 2 * dy;       // 选择东侧像素时的增量
        int incrNE = 2 * (dy - dx); // 选择东北侧像素时的增量

        int x = x0, y = y0;
        image.setRGB(x, y, color.getRGB());

        while (x < x1) {
            if (d <= 0) {
                d += incrE;
                x++;
            } else {
                d += incrNE;
                x++;
                y++;
            }
            image.setRGB(x, y, color.getRGB());
        }
    }

    /**
     * Wu反走样直线算法
     * 通过像素亮度加权减少锯齿感
     */
    public static void drawLineAntialiased(BufferedImage image, int x0, int y0, int x1, int y1, Color color) {
        boolean steep = Math.abs(y1 - y0) > Math.abs(x1 - x0);

        if (steep) {
            // 交换x和y
            int tmp = x0; x0 = y0; y0 = tmp;
            tmp = x1; x1 = y1; y1 = tmp;
        }
        if (x0 > x1) {
            // 确保从左向右绘制
            int tmp = x0; x0 = x1; x1 = tmp;
            tmp = y0; y0 = y1; y1 = tmp;
        }

        int dx = x1 - x0;
        int dy = y1 - y0;
        double gradient = dx == 0 ? 1.0 : (double) dy / dx;

        // 处理起点像素
        double intery = y0 + gradient;
        plot(image, steep, x0, y0, color, 1.0);

        // 处理中间像素
        for (int x = x0 + 1; x <= x1 - 1; x++) {
            plot(image, steep, x, (int)intery, color, 1.0 - (intery - (int)intery));
            plot(image, steep, x, (int)intery + 1, color, intery - (int)intery);
            intery += gradient;
        }

        // 处理终点像素
        plot(image, steep, x1, y1, color, 1.0);
    }

    private static void plot(BufferedImage image, boolean steep, int x, int y, 
                             Color color, double intensity) {
        int px = steep ? y : x;
        int py = steep ? x : y;
        if (px < 0 || px >= image.getWidth() || py < 0 || py >= image.getHeight()) return;

        int alpha = (int)(intensity * 255);
        Color c = new Color(color.getRed(), color.getGreen(), color.getBlue(), alpha);
        image.setRGB(px, py, c.getRGB());
    }

    /**
     * 测试主函数：绘制多条直线并保存为图片
     */
    public static void main(String[] args) throws Exception {
        int width = 400, height = 400;
        BufferedImage image = new BufferedImage(width, height, BufferedImage.TYPE_INT_ARGB);

        // 填充白色背景
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < height; j++) {
                image.setRGB(i, j, Color.WHITE.getRGB());
            }
        }

        // 绘制不同斜率的直线
        drawLine(image, 50, 50, 350, 50, Color.RED);      // 水平线
        drawLine(image, 50, 50, 50, 350, Color.GREEN);    // 垂直线
        drawLine(image, 50, 50, 350, 350, Color.BLUE);    // 对角线
        drawLine(image, 50, 350, 350, 50, Color.ORANGE);  // 反对角线
        drawLine(image, 50, 50, 350, 200, Color.MAGENTA); // 缓斜线
        drawLine(image, 50, 50, 200, 350, Color.CYAN);    // 陡斜线

        // 保存图片
        javax.imageio.ImageIO.write(image, "PNG", new java.io.File("bresenham_lines.png"));
        System.out.println("直线绘制完成，已保存到 bresenham_lines.png");
    }
}

算法复杂度分析

经典Bresenham算法是计算机图形学中最基础也是最重要的算法之一。它不仅在直线绘制中有广泛应用，其增量计算的思想还启发了后续的中点画圆算法、椭圆绘制算法以及三维光栅化算法。理解Bresenham算法对于深入学习计算机图形学管线具有里程碑式的意义。