Programming Interviews Exposed: Secrets to Landing Your Next Job, Second Edition

11.1. Graphics

A computer screen consists of pixels arranged in a Cartesian coordinate system. This is commonly called a raster pixel display. Computer graphics algorithms change the colors of sets of pixels. Often, the algorithm for generating a raster pixel image is based on a geometric equation. Because a computer screen has a finite number of pixels, translating from a geometric equation to a pixel display can be quite complex. Geometric equations usually have real-number (floating-point) solutions, but pixels are found only at fixed, regularly spaced locations. Therefore, every point that is calculated must be adjusted to pixel coordinates. This requires some kind of rounding, but rounding to the nearest pixel coordinate is not always the correct approach. It is often necessary to round numbers in unusual ways or add error-correcting terms. When rounding is done carelessly, it often leads to gaps in what should be continuous lines. Take care to check your graphics algorithms for distortion or gaps due to poor rounding or error correction.

Consider something as simple as drawing a line segment, for example. Suppose you were trying to implement a function that takes two endpoints and draws a line between them. After doing a little algebra, you could easily get an equation in the form of y = mx + b. Then, you could calculate y for a range of x values and draw the points making up the line. This function seems trivial.

The devil, though, is in the details of this problem. First, ...