矢量线的一种栅格化算法
charlee44 人气:0
[toc]
# 1. 概述
## 1.1. 已知算法
将一条线段栅格化的最简单的算法思路是根据其斜率，按X或Y方向步进取值：
![线的栅格化][imglink1]
![线的栅格化][imglink2]
除此之外还有一种算法是利用计算机图形学中绘制直线的Bresenham算法，这种算法的效率很高，原理就是用遍历的办法规避乘法和除法，只用加减法就能完成线段的栅格化。
## 1.2. 本文算法
上述两种算法有个问题就是都要经过一系列繁复的判断，才能得到比较严密的结果，所以我并没有采用。我这里采用的算法也是逐渐步进求值的办法，只不过不再沿着X或者Y方向求值，而是沿着射线方向步进。这里的射线指的是从线段的起点开始，以1像素为步进单位，步进到线段的终点。因为线段的方向性问题，步进得到的点总会有重复的值，最后再进行去重操作即可。
算法过程简述如下：
1. 设线段的起点为$O$，终点为$E$，则方向向量为$D=E-O$；
2. 线段的长度L为向量$D$的模。以0为初值，L为终值，以1为步进值建立一个for循环，每次取的长度为d;
3. 令$t=d/L$，则线段上相应的点为$P=O+tD$。这个公式是根据射线向量方程推导出来的，可以参看这篇文章[《已知线段上某点与起点的距离，求该点的坐标》][netlink1];
4. 将取的点都保存到容器中;
5. 对容器中的点进行去重操作。
最终得到的点即为直线栅格化后的点。
# 2. 实现
具体的C++实现代码如下：
```cpp
#include 加载全部内容