How to Code Your First Algorithm — Draw A Line

In this tutorial, of course, we will use JavaScript.After we get a good grasp on the algorithm visually, it’s time to start converting the logic into code.Here is the pseudo code: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*dyConverting it to JavaScript, we get the following: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; }};Note that all this is only for Quadrant 1.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.Then we calculate the delta of the line as a whole (here stored in variable D) — you can think of it as the mathematical equation for drawing a line..Or in other words the line slope equation.Before iterating through each span of the line, let’s reset the y-axis counter (that we will walk using a for-loop, as the line is being drawn) by setting it to the initial position on the line..Here y0 refers to the Y coordinate of the first point on the line.Finally, draw the line one “pixel” at a time, in pseudo code shown as pixel(x, y) function..Once the pixel is rendered, we can adjust the current pixel position using the delta steps we calculated.Every time the delta counter exceeds 0 we step down to the next pixel on the Y-axis and adjust the D variable again but in the opposite dimension, which ends up in progressively drawing the line across both dimensions until we reach the line’s end.But that’s not everything..In addition, depending on axis-dominance, the for-loop must be modified to travel in that direction..To complete the algorithm, we must also adjust parameters based on what octant (out of eight) we are in..This is explained in detail in the following section.Drawing In All 4 Quadrants / 8 OctantsThe 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.This means that in addition to the pseudo code above, we need to take care of two other things:Quadrant-Aware Algorithm..The algorithm must adjust iterator parameters, for each of the four quadrants..We can swap line endpoints to make sure that we always draw the line from left to right, and split the algorithm in two main parts (line is pointing either up or down from the starting point.) Or we can branch out in four different cases, for each quadrant respectively, and just swap x-axis and y-axis iterators to accommodate for line direction.Axis-Dominance..But even in each of the four quadrants, the line will either be x-axis or y-axis dominant.. More details

Leave a Reply