an elegant way to cover line segments with grids

Below is the code for clipping a line segment with grids. The idea is pretty straigtfoward. A line can be described by the formula in Fig. 1 parameterized by t. So We can represent a cuting point by t when we cut a line segment with the boundary of grids. The procedure in code consists of three steps. Firstly, we cut a line with the boundaries of grids parallel to x axis and insert the t to a set. And similarly, we cut a line with the boundaries of grids parallel to y axis and also insert the t to a set. Finally, we compute the coordinates of the clipping points according to Fig.1 and put them to a vector.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

set<double> t;
t.insert(0);t.insert(1);

for(int i = min(x1, x2)/GRID_LENGTH); i < max(x1, x2)/GRID_LENGTH; i++){//clip a line segment with boundary of grids
	if(!(x1=<i*GRID_LENGTH&&i*GRID_LENGTH<x2))continue;
	t.insert((i*GRID_LENGTH)/(x2-x1));
}

for(int j = min(y1, y2)/GRID_LENGTH); j < max(y1, y2)/GRID_LENGTH; j++){//clip a line segment with boundary of grids
	if(!(y1=<j*GRID_LENGTH&&i*GRID_LENGTH<y2))continue;
	t.insert((j*GRID_LENGTH)/(y2-y1));
}

set<double>::iterator it; double last_it;
vector<pair<double,double> > segment_points;
for(it = t.begin(); it != t.end(); it++){//insert clipping points to a vector
	if(it!=t.begin()&&abs(*it-last_it)<eps)continue;
	last_it = *it;
	segment_points.push_back(make_pair(x1+*it*(x2-x1), y1+*it*(y2-y1)));
}

After line segment clipping, the endpoints of a line is guaranteed to be lied in the grid. Without loss of generality, we represent a grid with its lower left corner coordinate. Therefore, we could quickly determine which grid the current line is located at by its midpoint.

set<pair<int, int> >grids;
grids.insert(make_pair(int(midpoint_x/GRID_LENGTH) - midpoint_x<0?1:0, int(midpoint_y/GRID_LENGTH) - midpoint_y<0?1:0))