Bresenham 算法

概述

Bresenham 是一个快速画直线的算法。在现实中，我们可以根据直线方程 $y = k x + b$ 画出任意直线，但在计算机中却稍有不同。由于计算机屏幕是由很多栅格（像素点）组成，所以直线在放大后会变成这个样子：

在这里插入图片描述
所以如何画出这样一条直线就成了问题。而 Bresenham 算法就可以快速解决这个问题。

设线段端点为 $x_1,y_1)$ ， $x_2,y_2)$ ， $\Delta x,\Delta y$ 为偏移量，直线方程为 $f (x) = k x + b$ 。则有：
$k=\frac{y_2-y_1}{x_2-x_1}=\frac{\Delta y}{\Delta x}$

假设已经确定了直线上某个点正好在像素 $P_i(x_i,y_i)$ ，我们要确定下一个像素 $P_{i+1}$ 是 $x_i+1,y_i)$ 还是 $x_i+1,y_i+1)$ 。此时的情况如下：

在这里插入图片描述
可以算出：

\begin{aligned} d_{1} & = f (x_{i} + 1) - y_{i} \\ d_{2} & = (y_{i} + 1) - f (x_{i} + 1) \\ d_{1} - d_{2} & = 2 k (x_{i} + 1) + 2 b - 2 y_{i} - 1 \end{aligned}

d_{1} d_{2} d_{1} - d_{2} = f (x_{i} + 1) - y_{i} = (y_{i} + 1) - f (x_{i} + 1) = 2 k (x_{i} + 1) + 2 b - 2 y_{i} - 1

我们可以把 $g(x_i)=d_1-d_2$ 作为决策函数，用来判断下一个像素点的坐标，则有：

$y_{i+1}=$

{\begin{cases} y_{i} & g (x_{i}) \leq 0 \\ y_{i} + 1 & g (x_{i}) > 0 \end{cases}

y_{i + 1} = {y_{i} y_{i} + 1 g (x_{i}) \leq 0 g (x_{i}) > 0

相关阅读:
基于微信花店鲜花商城小程序系统设计与实现开题报告
Java面试题及答案（2021年Java面试题大全带答案）
java之static关键字
深入理解与应用CSS clip-path 属性
ElasticSearch在windows环境启动
篇6：linux下GCC编译生成的可执行文件的步骤详解
SpringBoot整合JavaMailSender（发送QQ邮件）
自己制作智能语音机器人（基于jetson nano）
SpringBoot 快速整合spring-data-elasticsearch
重学Java8新特性(一) : Lambda表达式、常见函数式接口、方法引用

原文地址：https://blog.csdn.net/SP_FA/article/details/126109924