平面中直线和正方形算法

Question

求一个C++算法：
已知一个平面矩形，长宽分别是D和L。将这个矩形按照边长为d的正方形划分，如下图（正方形不一定铺满矩形，可以有多余的部分，多余的部分不计）

此时有一条线段ab，需要获取到这个线段ab经过了哪些正方形，得出这些正方形的坐标

Answer 1

1、找到线段与正方形边界的所有交点；
2、以这些交点将线段分为n个小段；
3、求每个小段的中点
4、判断中点所在的网格