javascriptalgorithmbresenham

Bresenham algorithm in Javascript


I need a fast algorithm for calculating coordinates for a line between two points. I tried to find good JavaScript Bresenham implementation, but there are too many and quite confusing publications. In wikipedia - here the fastest and most simple form (no divisions and error calculation for both directions) is presented in pseudocode like this:

 function line(x0, y0, x1, y1)
   dx := abs(x1-x0)
   dy := abs(y1-y0) 
   if x0 < x1 then sx := 1 else sx := -1
   if y0 < y1 then sy := 1 else sy := -1
   err := dx-dy

   loop
     setPixel(x0,y0)
     if x0 = x1 and y0 = y1 exit loop
     e2 := 2*err
     if e2 > -dy then 
       err := err - dy
       x0 := x0 + sx 
     if e2 <  dx then 
       err := err + dx
       y0 := y0 + sy 
   end loop

Do you know of a simple and robust JavaScript Bresenham implementation based on this pseudocode?


Solution

  • Rewriting your supplied pseudo-code into JavaScript:

    const { abs, sign } = Math;
    
    function line(x0, y0, x1, y1) {
      const dx = abs(x1 - x0);
      const dy = abs(y1 - y0);
      const sx = sign(x1 - x0);
      const sy = sign(y1 - y0);
      let err = dx - dy;
    
      while (true) {
        setPixel(x0, y0); // Do what you need to for this
    
        if (x0 === x1 && y0 === y1) break;
    
        const e2 = 2 * err;
        if (e2 > -dy) { err -= dy; x0 += sx; }
        if (e2 <  dx) { err += dx; y0 += sy; }
      }
    }
    

    Note that comparing floats directly may fail as you step (though it shouldn't when stepping by integer amounts, it might if either end point is non-integer), so instead of directly comparing the end points you might want to use an epsilon:

    const { abs, sign } = Math;
    const epsilon = 0.0001;
    
    function line(x0, y0, x1, y1) {
      ...
      while (true) {
        ...
        if (abs(x0 - x1) + abs(y0 - y1) < epsilon) break;
        ...
      }
    }
    

    This will necessarily slow you down, however, so only do this if you are dealing with non-integers.