2
\$\begingroup\$

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
        addToVector(xI, yI, setOfCellsToUnmark);
        //find coordinates that X axis is crossed by line from xA to xB exclusive
        addToVector(xI + MOVEMENT, yI, setOfCellsToUnmark);
    }
}
else {
    for (xI = coordinateToCellIndex(xA) * SIZE_CONST - MOVEMENT;
         xI > xB; xI -= SIZE_CONST) { 
        t = (xI - xA) / (xB - xA);
        yI = yA + t * (yB - yA);
        addToVector(xI, yI, setOfCellsToUnmark);
        addToVector(xI + MOVEMENT, yI, setOfCellsToUnmark);
    }
}

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);
        addToVector(xI, yI, setOfCellsToUnmark);
        addToVector(xI, yI + MOVEMENT, setOfCellsToUnmark);
    }
} else {
    for (yI = coordinateToCellIndex(yA) * SIZE_CONST - MOVEMENT;
         yI > yB; yI -= SIZE_CONST) { 
        t = (yI - yA) / (yB - yA);
        xI = xA + t * (xB - xA);
        addToVector(xI, yI, setOfCellsToUnmark);
        addToVector(xI, yI + MOVEMENT, setOfCellsToUnmark);
    }
}
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);
    }
}
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.