did a quick simple implementation of this algorithm
come down to just 33 loc, yeah.
The orange colored tiles get selected in addition to the blue when the CONSERVATIVE_RASTERISATION flag is set
https://docs.google.com/drawings/pub?id=1Jkah2jJduKdyFLC5kKRJ3dunGt6P7RKBsZjIB3_Su0Q&w=480&h=360
import java.awt.geom.Point2D;
import java.awt.geom.Point2D.Double;
import static java.lang.Math.*;
/**
*
* @author Daniel Heinrich <DannyNullZwo@gmail.com>
*/
public class Main
{
private static final boolean CONSERVATIVE_RASTERISATION = false;
private static class Line
{
final Point2D.Double start, end;
final double xshift;
public Line(Double s, Double e) {
start = s.y > e.y ? s : e; // ensures that the starting point of the lines is always above(>y) the end point
end = s.y > e.y ? e : s;
double mul = 1. / (start.y - end.y);
xshift = (end.x - start.x) * mul;
}
}
static void findCells(Line l) {
final double startXShift = l.xshift * (l.start.y - floor(l.start.y));//amount of x delta in the first tile of the line
final double endXShift = l.xshift * (ceil(l.end.y) - l.end.y);//amount of x delta in the last tile of the line
double x = l.start.x;
double y = l.start.y;
x = printTiles(x, x + startXShift, y);//gets all Tiles, in the row of the start point, which the line passes
y = floor(y) - 0.5;
while (y > ceil(l.end.y))// iterates over all rows which lie between the start and end point of the line
x = printTiles(x, x + l.xshift, y--);//gets all Tiles in the row which the line passes
printTiles(x, x + endXShift, y);//gets all Tiles, in the row of the end point, which the line passes
}
static double printTiles(double x1, double x2, double y) {
int firstTile, tileCount;
if (CONSERVATIVE_RASTERISATION) {
firstTile = (int) ceil((x2 > x1 ? x1 : x2) - 1.);
tileCount = (int) floor(abs(x2 - x1) + 1.) + 1;
} else {
firstTile = (int) floor((x2 > x1 ? x1 : x2));
tileCount = (int) ceil(abs(x2 - x1));
}
int tileYPos = (int) floor(y);
for (int i = 0; i < tileCount; ++i)
printTile(firstTile + i, tileYPos);
return x2;
}
static void printTile(int x, int y) {
System.out.println("[" + x + ',' + y + ']');
}
public static void main(String[] args) {
Line line = new Line(new Double(0, 2), new Double(4, 0));
findCells(line);
}
}
