teaching machines

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)

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *