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.

Here, I implemented my own ray cast algorithm and the I modified so every time a new row is visited, all required cells to the right of the new cell are also visited, and similarly with new columns. The code I wrote only works in the case where the ray has a vector with positive x and y coordinates. So if you want to use my code, you'll have to change it to make it work in every case; this is just a proof of concept. [EDIT: Skip down to `visit_cells_in_box_sweep' to get to the meat of the code.]

#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?

There were several details you got wrong. Here's a fixed version:

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/

I see the problem, but I disagree somewhat with your diagnosis. The issue is that a column is not visited until a square in that column is hit by the central ray. If you allow the ray to go much further (multiply t_max by 10 and allow 1000 iterations), you can't see the problem in the demo anymore.

Right now I am thinking that my code might be OK for a range of angles, say between 22.5 and 67.5 degrees. For vectors closer to being aligned with an axis, it's probably better to visit adjacent squares only in rows, to the left and to the right. But I suspect there is a more elegant solution waiting to be found.