Learn To Draw Your Own Lines (without canvas) — The Basic Principles Of Writing Algorithms

We often hear about algorithms, but there aren’t many tutorials that give you a sample demonstrating how to actually write one. Algorithms solve specific problems. In this case, we will draw a line on a custom raster “display” consisting of HTML elements. Of course, it is easier to simply use canvas, WebGL or some other library to draw lines. But by doing that you’re not really learning how to write your own. You will probably never have to write code to draw a line on the computer screen during your entire career as a web developer. But in this tutorial we’ll take a look at one of the most simple algorithms in computer history as an example to demonstrate the basic principles!

Here’s a list of my best web development tutorials.

Why Bresenham’s Line Drawing Algorithm?

I think it’s a perfect specimen to learn from for many reasons:

  1. It’s relatively simple as your first example to study algorithms from.
  2. It uses the Cartesian Coordinate System — the one used as the basis in many popular algorithms. It’s prerequisite to Machine Learning (which uses so called activation functions in AI, which are CCS-based math equations.)
  3. You can implement it in JavaScript (see the live demo here.)

How Does It Work?

Algorithms are tricky beasts.

This algorithm solves line drawing for Quadrant 1 on the Cartesian Coordinate System.

Why Draw Lines in HTML Without Canvas?

Many reasons!

Implementing Line Drawing Algorithm in JS

We take two deltas and calculate the slope of the line equation, based on two end points of the line.

draw_line(x0, y0, x1, y1)// Calculate "deltas" of the line (difference between two ending points)
dx = x1 - x0
dy = y1 - y0
// Calculate the line equation based on deltas
D = (2 * dy) - dx
y = y0
// Draw the line based on arguments provided
for x from x0 to x1
// Draw pixel at this location
pixel(x, y)
// Progress the line drawing algorithm parameters
if D > 0
y = y + 1
D = D - 2*dx
end if
D = D + 2*dy
let draw_line = (x0, y0, x1, y1) => {// Calculate "deltas" of the line (difference between two ending points)
let dx = x1 - x0;
let dy = y1 - y0;
// Calculate the line equation based on deltas
let D = (2 * dy) - dx;
let y = y0;// Draw the line based on arguments provided
for (let x = x0; x < x1; x++)
{
// Place pixel on the raster display
pixel(x, y);
if (D >= 0)
{
y = y + 1;
D = D - 2 * dx;
}
D = D + 2 * dy;
}
};

Algorithm Logic Explanation:

First we calculate the difference between the line’s end points on both axes (dx and dy) which are usually referred to as the deltas — for each of the two dimensions, respectively.

Drawing In All 4 Quadrants / 8 Octants

The barebones Bresenham’s line algorithm above is designed to draw a line only in one quadrant (Quadrant 1) of the Cartesian coordinate system. But we need to cover all directions. After all, a random line can be plotted from any point on the raster screen to any other point.

  • Axis-Dominance. But even in each of the four quadrants, the line will either be x-axis or y-axis dominant. This means there are actually not four but eight different cases. One for each of the eight octants. Luckily, the algorithm stays exactly the same, all we need to do is switch the iterators and branch out a few times.

The Complete Bresenham’s Algorithm In JavaScript

Okay — all of this sounds great in theory — and we already covered the pseudo code and JavaScript version — but only for one quadrant! Let’s take a look at the whole enchilada.

let draw_line = (x1, y1, x2, y2) => {// Iterators, counters required by algorithm
let x, y, dx, dy, dx1, dy1, px, py, xe, ye, i;
// Calculate line deltas
dx = x2 - x1;
dy = y2 - y1;
// Create a positive copy of deltas (makes iterating easier)
dx1 = Math.abs(dx);
dy1 = Math.abs(dy);
// Calculate error intervals for both axis
px = 2 * dy1 - dx1;
py = 2 * dx1 - dy1;
// The line is X-axis dominant
if (dy1 <= dx1) {
// Line is drawn left to right
if (dx >= 0) {
x = x1; y = y1; xe = x2;
} else { // Line is drawn right to left (swap ends)
x = x2; y = y2; xe = x1;
}
pixel(x, y); // Draw first pixel// Rasterize the line
for (i = 0; x < xe; i++) {
x = x + 1;
// Deal with octants...
if (px < 0) {
px = px + 2 * dy1;
} else {
if ((dx < 0 && dy < 0) || (dx > 0 && dy > 0)) {
y = y + 1;
} else {
y = y - 1;
}
px = px + 2 * (dy1 - dx1);
}
// Draw pixel from line span at
// currently rasterized position

pixel(x, y);
}
} else { // The line is Y-axis dominant// Line is drawn bottom to top
if (dy >= 0) {
x = x1; y = y1; ye = y2;
} else { // Line is drawn top to bottom
x = x2; y = y2; ye = y1;
}
pixel(x, y); // Draw first pixel// Rasterize the line
for (i = 0; y < ye; i++) {
y = y + 1;
// Deal with octants...
if (py <= 0) {
py = py + 2 * dx1;
} else {
if ((dx < 0 && dy<0) || (dx > 0 && dy > 0)) {
x = x + 1;
} else {
x = x - 1;
}
py = py + 2 * (dx1 - dy1);
}
// Draw pixel from line span at
// currently rasterized position

pixel(x, y);
}
}
}

pixel(x, y)

Remember, we are not using canvas or any other graphics library when writing our own graphics algorithms.

Final Words

Often, people ask me how to improve their coding skills. I usually suggest choosing a project slightly above the range of your current ability. If you make sure to finish it, this experience will help you advance your coding skills. For me, this was that type of project.

Issues. Every webdev has them. Published author of CSS Visual Dictionary https://amzn.to/2JMWQP3 few others…

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store