badd10de.dev

Data Structures and Algorithms


Sorting

Some rules of thumb for selecting sorting algorithms:

Resources

Hash tables/Hashing

Resources

Random/Pseudo random

Resources

Graphics

Bresenham’s algorithm for rasterizing lines

  1. Get the initial (x0, y0) and final (x1, y1) coordinates for the line.
  2. Calculate the deltas delta_x, delta_y, 2 * delta_x and 2 * delta_y
  3. Initialize initail error parameter as: err = 2_delta_y - delta_x
  4. For each x coordinate point between x0 and x1 (x_k) if err < 0 the next point is (x_k + 1, y_k); err = err + 2_delta_y. If not, `(x_k + 1, y_k
    • 1); err = err + 2_delta_y - 2_delta_x`

The previous algorithm will only work when drawing lines in the same direction. Additionally, the inputs may be flipped (e.g. x1 < x0) and the slope can be positive or negative. Here is a C implementation of the line drawing algorithm with these considerations in mind, using exclusively integer arithmetic:

// Draws a line with the given color between (x0,y0) and (x1,y1) using the
// Bresenham's line drawing algorithm using exclusively integer arithmetic.
static void
draw_line(int x0, int y0, int x1, int y1, Color clr) {
    // Pointer to the initial position of the screen buffer where we will start
    // writing our data.
    vu16 *destination = (u16*)(SCREEN_BUFFER + y0 * SCREEN_WIDTH + x0);

    // Adjust the step direction and calculate deltas.
    int x_step;
    int y_step;
    int dx;
    int dy;
    if (x0 > x1) {
        x_step = -1;
        dx = x0 - x1;
    } else {
        x_step = 1;
        dx = x1 - x0;
    }
    if (y0 > y1) {
        y_step = -SCREEN_WIDTH;
        dy = y0 - y1;
    } else {
        y_step = +SCREEN_WIDTH;
        dy = y1 - y0;
    }

    if(dy == 0) {
        // Horizontal line.
        for(int i = 0; i <= dx; i++) {
            destination[i * x_step] = clr;
        }
    } else if(dx == 0) {
        // Vertical line.
        for(int i = 0; i <= dy; i++) {
            destination[i * y_step] = clr;
        }
    } else if (dx >= dy){
        // Positive slope.
        int diff = 2 * dy - dx;
        for (int i = 0; i <= dx; ++i) {
            *destination = clr;
            if (diff >= 0) {
                destination += y_step;
                diff -= 2 * dx;
            }
            destination += x_step;
            diff += 2 * dy;
        }
    } else {
        // Negative slope.
        int diff = 2 * dx - dy;
        for (int i = 0; i <= dy; ++i) {
            *destination = clr;
            if (diff >= 0) {
                destination += x_step;
                diff -= 2 * dy;
            }
            destination += y_step;
            diff += 2 * dx;
        }
    }
}

Other

Resources