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

相关阅读:
商标申请注册交费就一定会下注册证？
Hudi第二章：集成Spark(二)
C++11之继承构造函数（using 声明）
深度剖析动态规划算法：原理、优势与实战
堆排序+TOPK问题
毛玻璃态按钮悬停效果
【Linux03-基本工具之make和makefile】Linux下的项目构建工具+进度条小程序
基于SpringBoot的摄影跟拍预定管理系统
万字长文：一文彻底搞懂Elasticsearch中Geo数据类型查询、聚合、排序
1个月写900多条用例，二线城市年薪33W+的测试经理能有多卷？

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