Moving along lines

[sargon94]

Many people know what a line is, and many more can draw them using slope. But I've noticed that when trying to draw a line using only the origin and end points, people stumble and fall.

The question is quite simple: How can I draw something without a concrete x and y coordinate?

The answer is also simple: You find them.

Let us imagine you wish to move an object from the origin point (0,0) to a certain end point (8,20). Well, a human would simply realize that (8, 20) translates into a slope of 2/5 (2 up, 5 right) and draw the line accordingly. Unfortunatly, a computer doesn't possess a ruler with which to draw the line. So the person is forced to tell the computer every single point the line goes through. This is done quite easily. In this example, we are moving up and over. So, we already have the Y coordinates. They are points 1 through 20.

But how to get X? It's easy, X is a function of Y. Like so: X=(X1/Y1)*Y

To get a better idea:

X= X1 * Y
__Y1

In this equation, X1 is 8 (the target point's X coordinate) and Y1 is 20 (the target point's Y coordinate). As for Y, simply substitute 1 through 20 to get the X coordinates for it.

The program sample would look like this:

float X1=8, Y1=20;
     float x[20], y[20];
     for (int i=1; i<21; i++)
     {
         y[i]=i;
         x[i]=(X1/Y1)*y[i];
     }
     for (int i=1; i<21; i++)
     {
         cout<<"y["<<i<<"]="<<y[i]<<" x["<<i<<"]="<<x[i]<<endl;
     }

Which creates the following output:

y[1]=1 x[1]=0.4
y[2]=2 x[2]=0.8
y[3]=3 x[3]=1.2
y[4]=4 x[4]=1.6
y[5]=5 x[5]=2
y[6]=6 x[6]=2.4
y[7]=7 x[7]=2.8
y[8]=8 x[8]=3.2
y[9]=9 x[9]=3.6
y[10]=10 x[10]=4
y[11]=11 x[11]=4.4
y[12]=12 x[12]=4.8
y[13]=13 x[13]=5.2
y[14]=14 x[14]=5.6
y[15]=15 x[15]=6
y[16]=16 x[16]=6.4
y[17]=17 x[17]=6.8
y[18]=18 x[18]=7.2
y[19]=19 x[19]=7.6
y[20]=20 x[20]=8

[hamsterman]

And when Y1 == 0... ?

To be honest I'm not sure what are you trying to do. It looks like you want to get the coordinates of pixels on the line, but then x and y should be ints.
If you want to do that, the right way would be to take the longer of the two sides. That way there is no division by 0 and no gaps in the line.

int num = max(x1, y1);//how many points to draw?
//if we take the lesser of x1, y1 our line would have gaps

for(int i = 0; i < num; i++){
   x[i] = i*x1/num;
   y[i] = i*y1/num;
}

[hanst99]

Actually, why don't you juse use a linear interpolation here? That's high school level math, easy to use, doesn't need any more code, and doesn't require divisions. Oh, and of course you also don't need arrays for it.

[hamsterman]

This already is linear interpolation (between points 0; 0 and x1; y1)
Divisions are inevitable. Array is optional.

[Disch]

I just noticed the OP i using 1-based indexes and therefore is overflowing his array.

Shame on him!

[moorecm]

Way back in the DOS days, you might find yourself writing an algorithm to draw a line. These days, not so much. It's interesting, though. If I recall, most implementations of this I've seen separate the various cases (horizontal, positive slope, negative slope, vertical).

[hanst99]

This already is linear interpolation (between points 0; 0 and x1; y1)
Divisions are inevitable. Array is optional.

Pseudocode:

lin_interpol (point1, point2,k) 
begin
resultpoint.x = point1.x * k + point2.x *(1-k)
resultpoint.y = point1.y * k + point2.y*(1-k)
end

- of course k must be between 0 and 1 here.

The only necessary division is to calculate k for any specific point (e.g. if you wanted k for pixels). Then the division would be done in the client code, where the caller has the necessary control to ensure a division by 0 wouldn't occur
ex for pixels:

pxlDist = max(abs(point1.x -point2.x),abs(point1.y-point2.y))
for i = 0 to pxlDist
begin
draw_point(lin_interpol(point1,point2,i/pxlDist)
end

I have full control over here. Unlike in the OPs code, a division by 0 will never occur here and there is no array necessary (if the user wanted one, he could simply make one). It's also not limited to a line from the origin point.

[ultifinitus]

I believe that in this case the line drawing is used to calculate the position of the bullets in his game...

If I were to do the same thing, I would just calculate the necessary velocity and apply that to my object. Barring friction, it would work perfectly. That way you wouldn't have to calculate every single position, just simply add your velocity to your current position, I would also base both off of a float or double, rather than truncating to an int value.

[hanst99]

I think it was actually about drawing a line here, I doubt anyone is unable to move an object along a line.

[ultifinitus]

sargon94 wrote:

Let us imagine you wish to move an object from the origin point (0,0) to a certain end point (8,20).

Lol, I don't know hanst =)

[hanst99]

Right above that,

But I've noticed that when trying to draw a line using only the origin and end points

though.

[ultifinitus]

That's completely true, I can see your perspective, how about we ask him?

@sargon: answer?

[ne555]

No divisions, just integer addition, subtraction and bit shifting
http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm