Sounds like you're doing the equivalent of drawing a line between two points. And, indeed, straightforward approaches such as picking midpoints recursively or moving between the two points "a little bit at a time" are not very appealing. I'm sure you can adapt Breshenham's line drawing algorithm to the task:
http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
The essential feature of the algorithm is to look at the two points and decide if the line mostly moves in X or in Y. That is, "mostly X" means the line is closer to horizontal, "mostly Y" means closer to vertical. It then guarantees that every iteration gives you a new pixel and it will move exactly the number of pixels in the X (or Y) direction as necessary.
And, besides, it's way cool.