首页 / 软件开发 / 数据结构与算法 / 算法系列（十） 直线生成算法

算法系列（十） 直线生成算法2014-04-30 csdn博客 吹泡泡的小猫在欧氏几何空间中，平面方程就是一个三元一次方程，直线就是两个非平行平面的交线，所以直线 方程就是两个三元一次方程组联立。但是在平面解析几何中，直线的方程就简单的多了。平面几何中 直线方程有多种形式，一般式直线方程可用于描述所有直线：

Ax+By+C = 0  （A、B不同 时为0）

当知道直线上一点坐标（X0，Y0）和直线的斜率K存在时，可以用点斜式方程：

Y-Y0 = K（X – X0） （当K不存在时，直线方程简化成X = X0）

当知道直线上的两个点 （X0,Y0）和（X1,Y1）时，还可以用两点式方程描述直线：

除了这三种形式的直线方程外，直线方 程还有截距式、斜截式等多种形式。

在数学范畴内的直线是由没有宽度的点组成的集合，但是 在计算机图形学的范畴内，所有的图形包括直线都是输出或显示在点阵设备上的，被成为点阵图形或 光栅图形。以显示器为例，现实中常见的显示器（包括CRT显示器和液晶显示器）都可以看成由各种颜 色和灰度值的像素点组成的象素矩阵，这些点是有大小的，而且位置固定，因此只能近似的显示各种 图形。图（1）就是对这种情况的一种夸张的放大：

图（1）直线在点阵设备上的表现形式

计算机图形学中的直线生成算法，其实包含了两层 意思，一层是在解析几何空间中根据坐标构造出平面直线，另一层就是在光栅显示器之类的点阵设备 上输出一个最逼近于图形的象素直线，而这就是常说的光栅图形扫描转换。本文就是介绍几种常见的 直线生成的光栅扫描转换算法，包括数值微分法（DDA法）、Bresenham算法、对称直线生成算法以及 两步算法。