I think what you are suggesting is a ray cast algorithm? If so, I already have an efficient implementation of ray cast that contains no overlaps and generate cells based on the the order they are traversed. Multiple ray casts is of course an solution to this problem but they have 2 main disadvantages. First they return duplicates, second they do not generate cells based on the order they are traversed (as you are doing 1st ray -> 2nd ray etc... ) and thus you can not bail out early if something is already hit.

#include <iostream>
#include <cmath>

struct Vector {
  float x, y;
 
  Vector(float x, float y) : x(x), y(y) {
  }
};

Vector operator*(float s, Vector const &v) {
  return Vector(s * v.x, s * v.y);
}

float dot(Vector const &v1, Vector const &v2) {
  return v1.x * v2.x + v1.y * v2.y;
}

float length(Vector const &v) {
  return std::sqrt(dot(v,v));
}

Vector normalized(Vector const &v) {
  return (1.0f / length(v)) * v;
}

struct Point {
  float x, y;
 
  Point(float x, float y) : x(x), y(y) {
  }
};

Point operator+(Point const &p, Vector const &v) {
  return Point(p.x + v.x, p.y + v.y);
}

struct Ray {
  Point p;
  Vector v;
 
  Ray(Point const &p, Vector const &v) : p(p), v(v) {
  }
 
  Point at(float t) const {
    return p + t * v;
  }
};

struct Cell {
  int x, y;
 
  Cell(int x, int y) : x(x), y(y) {
  }
 
  Cell() = default;
 
  Cell(Cell const &) = default;
};

bool operator==(Cell const &c1, Cell const &c2) {
  return c1.x == c2.x && c1.y == c2.y;
}

bool operator!=(Cell const &c1, Cell const &c2) {
  return !(c1 == c2);
}

template <typename Function>
void visit_cells_in_box_sweep(Ray const &ray, float half_width, Function f, float max_t) {
  float A = ray.v.y;
  float B = -ray.v.x;
  float min_C = A * (ray.p.x - half_width) + B * (ray.p.y + half_width);
  float max_C = A * (ray.p.x + half_width) + B * (ray.p.y - half_width);
 
  float next_horizontal = std::fmod(1.0f - ray.p.y, 1.0f) / ray.v.y;
  float next_vertical = std::fmod(1.0f - ray.p.x, 1.0f) / ray.v.x;
  Cell last_cell(int(std::floor(ray.p.x)), int(std::floor(ray.p.y)));
 
  while (1) {
    float next = std::min(next_horizontal, next_vertical);
    if (next >= max_t)
      break;
    
    Point intersection = ray.at(next);
    
    Cell cell;
    if (next_horizontal < next_vertical) {
      next_horizontal += 1.0f / ray.v.y;
      cell = Cell(int(std::floor(intersection.x)), int(std::round(intersection.y)));
    }
    else {
      next_vertical += 1.0f / ray.v.x;
      cell = Cell(int(std::round(intersection.x)), int(std::floor(intersection.y)));
    }
    if (cell.y > last_cell.y) {
      // New row
      for (int x = cell.x - 1; A * (x + 1) + B * cell.y >= min_C; --x)
    f(Cell(x, cell.y));
    }
    if (cell.x > last_cell.x) {
      // New columns
      for (int y = cell.y - 1; A * cell.x + B * (y + 1) <= max_C; --y)
    f(Cell(cell.x, y));
    }
    if (cell != last_cell)
      f(cell);
    last_cell = cell;
  }
}

void print_cell(Cell const &cell) {
  std::cout << "Visiting cell at (" << cell.x << "," << cell.y << ")\n";
}

int main() {
  Ray ray(Point(10.75f, 5.5f), normalized(Vector(0.5f, 1.0f)));
  visit_cells_in_box_sweep(ray, 0.5f, print_cell, 10.f);
}

Hi, I implemented your algorithm here : http://jsfiddle.net/u0456cpu/1/, it doesnt seem to be working.

Did I do something wrong?

function visit_cells_in_box_sweep(x, y, vx, vy, halfWidth, max_t){
    var floor = Math.floor;
    var min = Math.min;

    var A = vy;
    var B = -vx;
    var min_C = A * (x - halfWidth) + B * (y + halfWidth);
    var max_C = A * (x + halfWidth) + B * (y - halfWidth);
    var next_horizontal = fmod(1.0 - y, 1.0)/vy;
    var next_vertical = fmod(1.0 - x, 1.0)/vx;

    var last_cell_x = floor(x);
    var last_cell_y = floor(y);

    var _ = 100; // break out of infinite loop just in case
    while (_>0){
        _--;
        var next = min(next_horizontal, next_vertical);
        if (next >= max_t)
            break;
        var rx = x + next * vx;
        var ry = y + next * vy;
        var cx;
        var cy;
        if (next_horizontal < next_vertical){
            next_horizontal += 1.0/ vy;
            cx = floor(rx);
            cy = floor(ry+.5);
        } else {
            next_vertical += 1.0/ vx;
            cx = floor(rx+.5);
            cy = floor(ry);
        }
        
        if (cy > last_cell_y){
            // new row
            for (var _x = cx - 1; A * (_x+1) + B * cy >= min_C; --_x){
                plotColored(_x, cy, 10, "red");
                //console.log(_x, _y);
            }
        }
        if (cx > last_cell_x){
            // new columns
            for (var _y = cy - 1; A * cx + B * (_y+1) <= max_C; --_y){
                plotColored(cx, _y, 10, "blue");
                //console.log(cx, _y);
            }
        }
        
        if (cx !== last_cell_x || cy !== last_cell_y){
            plotColored(cx, cy, 10, "black");
           // console.log(cx,cy);
            last_cell_x = cx;
            last_cell_y = cy;
        }
    }

    x *= 10;
    y *= 10;
    vx *= 10;
    vy *= 10;
    halfWidth *= 10;
    ctx.beginPath();
    ctx.moveTo(x,y);
    ctx.lineTo(y+vx,y+vy);
    ctx.closePath();
    ctx.strokeStyle = "red";
    ctx.stroke();

    ctx.strokeRect(x-halfWidth, y-halfWidth, halfWidth*2, halfWidth*2);
}

Thanks for fixing it up! I was doing it more for curiosity than anything else. Pretty neat algorithm. Too bad it is a few days too late for me . Still, I am sure others may find it useful.

Actually now that I tested your algorithm a little, I found it missing cells when vx or vy is very small. I think this is because you are only tracing the ray from center of box then appending the row and columns. So if vx or vy is very small, the ray from center of box may still be in the same row/column. Whereas a ray from the corner of box may have intercepted other cells.

Oh and here is the fixed version for future reference: http://jsfiddle.net/u0456cpu/2/