# Find cells crossed by a line

This method find cells that are crossed by line A-B and adds them to one vector. I have got some duplicates here and some lines of code are very similiar but they differ in one variable. Should this duplicated be fixed or is it fine?

std::vector<Cell> Grid::findCells(int xA,int yA,  int xB,  int yB) {

vector<Cell> setOfCellsToUnmark;
//
int xI, yI, t;

if (xA < xB) {
for (xI = coordinateToCellIndex(xA) * SIZE_CONST + MOVEMENT;
xI < xB; xI += SIZE_CONST) {
t = (xI - xA) / (xB - xA);
yI = yA + t * (yB - yA);
//find coordinates that X axis is crossed by line from xA to xB inclusive
//find coordinates that X axis is crossed by line from xA to xB exclusive
}
}
else {
for (xI = coordinateToCellIndex(xA) * SIZE_CONST - MOVEMENT;
xI > xB; xI -= SIZE_CONST) {
t = (xI - xA) / (xB - xA);
yI = yA + t * (yB - yA);
}
}

if (yA < yB) {
for (yI = coordinateToCellIndex(yA) * SIZE_CONST + MOVEMENT;
yI < yB; yI += SIZE_CONST) {
t = (yI - yA) / (yB - yA);
xI = xA + t * (xB - xA);
}
} else {
for (yI = coordinateToCellIndex(yA) * SIZE_CONST - MOVEMENT;
yI > yB; yI -= SIZE_CONST) {
t = (yI - yA) / (yB - yA);
xI = xA + t * (xB - xA);
}
}
return setOfCellsToUnmark;
}

void Grid::addToVector(const int x, const int y, vector<Cell> & setOfCells) const {
Cell c = coordinateToCellIndex(x, y);
if (isCellInGrid(c)) {
setOfCells.push_back(c);
}
}


What you're implementing is called Bresenham's Line Algorithm.

You can get rid of the duplication by implementing the algorithm as described on wikipedia. Mirrored here for completeness:

 function line(x0, y0, x1, y1)
real deltax := x1 - x0
real deltay := y1 - y0
real error := 0
real deltaerr := abs(deltay / deltax)    // Assume deltax != 0 (line is not vertical),
// note that this division needs to be done in a way that preserves the fractional part
int y := y0
for x from x0 to x1
plot(x,y)
error := error + deltaerr
while error ≥ 0.5 then
plot(x, y)
y := y + sign(y1 - y0)
error := error - 1.0


If you want to, you can also look at my implementation here.