# Algorithm for spacing points out among a line

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.

• Are you maybe looking for this line drawing algorithm? – sam hocevar Jul 13 '16 at 8:09
• @samhocevar YES! Exactly what I'm looking for! – user82739 Jul 13 '16 at 8:19

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!

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

• This only works if I know what fractions I should set each point at, which I do not. This is what I am asking to find out. How to find the fractions of each point, to make the line as closely resemble the desired angle as possible. – user82739 Jul 13 '16 at 7:01
• @MitchWeaver Sorry did not get that will update the anser – Blindman67 Jul 13 '16 at 7:22