How different can the number of pixels in a straight line be to its real length?

Question

I'm working on a game with a programmable robot. It uses a laser range finder to get the distance to walls.

I'm using DDA to generate a line from the robot, going in the direction it is pointing, then checking each pixel along the line to see if it hits anything. At that point, the number of pixels checked so far is used as the range, to save having to calculate the proper length.

If the line is horizontal or vertical, then there's no discrepancy, but how greatly does the number of pixels in a line differ from its real length in the worst case?

Notes:

• The length of the line is never just a few pixels, say always at least 50px.
• Longer lines obviously have larger discrepancies, but the question is really about relative differences.

Answer 1

The worst case is when the line is at a 45-degree angle; then its length (in pixel-sized units) is a factor of $\sqrt{2}$ times the number of pixels, or about 40% longer.

You can see this if you imagine starting with a vertical line of say 50px, then gradually sliding the endpoint away horizontally. Note that the number of pixels drawn doesn't change! You still have exactly one pixel turned on in each row that the line crosses. The pixels will adjust their horizontal positions but no new pixels will turn on, until the line surpasses 45 degrees from the vertical. The same is true if you start with a horizontal line and slide the endpoint vertically.

The number of pixels in the line effectively only looks at the vertical or horizontal distance, whichever is larger, and ignores the smaller dimension. Mathematically, the number of pixels is $\max(|\Delta x|, |\Delta y|)$ while the Euclidean distance is $\sqrt{\Delta x^2 + \Delta y^2}$.