# Algorithm for spacing points out among a line

by Mitch Weaver   Last Updated July 13, 2016 08:05 AM

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.

Tags :

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....
``````

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){
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!