Drawing a line
I have a friend who is trying to get a bunch of first semester programmers to plot a line between two points into a 2-D pixel array. Bresenham’s is out of the question. A first attempt was a slope-based approach. I never saw the code he came up with, but it wasn’t able to handle non-functions. (The only non-function line I know is a vertical one, in which the run of the line is 0 and slope is infinite.)
The second and current attempt, suggested by one of our students, is to consider one of the points the center of a circle and to express the the second point as a polar coordinate:
theta = atan2(diffY, diffX)
distance = (diffY ^ 2 + diffX ^ 2) ^ 0.5
The first equation is what it is because tan(theta) = opposite / adjacent = rise / run = diffY / diffX.
The next step is to iterate along the distance, turning the ever-lengthening polar vector back into its Cartesian components at each step:
for sample in 0:0.01:distance
plot(x1 + d * cos(theta), y1 + d * sin(theta))
The solution works, but I don’t find it intuitive. I believe a pure Cartestian vector approach is more understandable (and probably more efficient!). If we observe that cos(theta) = diffX / distance and sin(theta) = diffY / distance, then we can substitute these values into the above algorithm:
diffX = x1 - x2
diffY = y1 - y2
distance = ...
for d in 0:0.01:distance
plot(x1 + d * diffX / distance, y1 + d * diffY / distance)
This still doesn’t strike me as very intuitive. We can think of d / distance semantically as the proportion of the hypotenuse that we have traversed. Let’s factor that out and give it a more meaningful name:
for d in 0:0.01:distance
proportion = d / distance
plot(x1 + proportion * diffX, y1 + proportion * diffY)
This solution seems more intuitive to me. I think it’d be easy to arrive at directly, though here I derived it from my friend’s existing solution to prove its equivalence.
We could complicate/simplify a bit further if we loop over the proportion directly. The number of steps our loop takes is distance / 0.01. Our proportion value goes from 0 to 1, so to get the proportion step, we break that range (1 – 0) up into nsteps steps:
nsteps = distance / 0.01
step = 1 / nsteps
for proportion in 0:step:1
plot(x1 + proportion * diffX, y1 + proportion * diffY)