Algorithm for spacing points out among a line

Question

I'm writing an angled tile system, and my implementation is to have a starting height and an ending height inside the tile.

Like so:

The starting and ending height allow me to get the length of the angle and the angle in degrees using atan2.

For collision against the angled tiles I give the tiles a collection of points along the line, and as a bounding box intersects any of a tile's slope points it will move the box's y position to that point.

This implementation works fine for 45 degree tiles, however with other degrees I don't know how to create the points on the line.

What algorithm could I use to space the points out along the line when they are not in a perfect 1 to 1 ratio angle? (e.g. 17 degrees instead of a nice 45 degrees)

EDIT: Here's a way to interpret my question perhaps more academically:

Given a length of a line and its angle, and an arbitrary number of points, find an algorithm that will space the points out among the line that will as closely resemble the angle.

Answer 1

My solution, using the Brensenham algorithm as suggested by Sam Hocevar:

public static Point[] brensenham(Point p1, Point p2) {
        final ArrayList<Point> points = new ArrayList<Point>();

        // BRENSENHAM the line across
        final int dx =  abs(p2.x-p1.x), sx = p1.x<p2.x ? 1 : -1;
        final int dy = -abs(p2.y-p1.y), sy = p1.y<p2.y ? 1 : -1; 
        int err = dx+dy, e2; /* error value e_xy */

        while(true){
            points.add(new Point(p1.x, p1.y));
            if (p1.x==p2.x && p1.y==p2.y) break;
            e2 = 2*err;
            if (e2 >= dy) { err += dy; p1.x += sx; } /* e_xy+e_x > 0 */
            if (e2 <= dx) { err += dx; p1.y += sy; } /* e_xy+e_y < 0 */
        }

        return points.toArray(new Point[points.size()]);
    }

This returns a PERFECTLY spaced out line of points, with the perfect number of points in integer coordinates that most similates the original angle between the starting points.

Hope this can help anyone else, it made for a very easy angled tile system!

Answer 2

To space points on a line can be done several ways.

Where the line is defined with

x1 = ?  // line start
y1 = ? 
x2 = ?  // line end
y2 = ?

To get a point on the line via a fraction of the line length

pointAt = ? // 0 to 1 are on the line 
            // less than 0 is before the line greater than 1 is after the line

px = (x2-x1) * pointAt + x1;
py = (y2-y1) * pointAt + y1;

To get a point a set distance along the line get the normalized vector of the line

distOnLine = ?
nx = x2-x1
ny = y2-y1
lengthOfLine = sqrt(nx * nx + ny * ny)
if(lengthOfLine > 0){ // make sure the line has length
   nx /= lengthOfLine // normalise the vector
   ny /= lengthOfLine
   px = x1 + nx * distOnLine
   py = y1 + ny * distOnLine
}

To get points on the line a specific x coordinates find the slope of the line in terms of x

findPointForX = ?
if(x1 !== x2){ // make sure the line is not vertical
    slope = (y2-y1)/(x2-x1)
    px = findPointForX
    py = (findPointForX - x1) * slope + y1
}

For y just swap x for y in the above

Think that covers most of the situations. If you want to divide a line into equal segments use the first method and set the fraction as multiples of 1/steps.

If you want a point on a line at an angle

distOnLine = ? // where on the line in pixels
x1 = ?  // the line start
y1 = ?
angle = ?  // the angle in radians

px = cos(angle) * distOnLine + x1
py = sin(angle) * distOnLine + y1

To convert to radians from deg

rad = deg / (180 / PI) // where PI is 3.1415....