Proof of Bresenham / Mid-Point formula

Another way to derive the line drawing algorithm is incrementally.

Assumptions:

* x0 < x1
* y0 < y1

Line has slope, m = dy/dx, less than 45 degrees (Zeroth octant)

 \  |  /
  \2|1/
  3\|/0
 ---+---
  4/|\7
  /5|6\
 /  |  \


Let's start with a "dumb" line drawing:

function line( x0, y0, x1, y1 )
  y = y0;
  for x = x0 to x1
      putpixel( x, y )

Unfortunately this just draws a horizontal line. :-/
What we want is this:

  y = y0;
  for x = x0 to x1
      putpixel( x, y )
      figure out new y

Sometimes we increment y, sometimes we don't:

  y = y0;
  for x = x0 to x1
      putpixel( x, y )
      if( incrementY )
          y = y + 1

If we use floating-point this becomes easy if we keep track of the error:

function line( x0, y0, x1, y1 )
  dy = y1 - y0;
  dx = x1 - x0;
  y = y0;

  e = 0;
  m = dy/dx; // traditional slope
  for x = x0 to x1
      putpixel( x, y )
      e += m;
      if (e > 0.5)
          e = e - 1
          y = y + 1

We want to get rid of that 0.5. We multiply m by 2:

  dy = y1 - y0;
  dx = x1 - x0;
  y = y0;

  e = 0;
  m = 2*dy/dx;
  for x = x0 to x1
      putpixel( x, y )
      e += m;
      if (e > 1)
          e = e - 2
          y = y + 1

We also want to get rid of that division -- we need to multiply all the terms by dx;
this means all terms involving m need to be updated:

  dy = y1 - y0;
  dx = x1 - x0;
  y = y0;

  e = 0;
  m = 2*dy;
  for x = x0 to x1
      putpixel( x, y )
      e += m;
      if (e > dx)
          e = e - 2*dx
          y = y + 1

We also want to compare the sign instead of 'e > dx' -- we can change that by offsetting the initial term.

  dy = y1 - y0;
  dx = x1 - x0;
  y = y0;

  e = -dx;
  m = 2*dy;
  for x = x0 to x1
      putpixel( x, y )
      e += m;
      if (e > 0)
          e = e - 2*dx
          y = y + 1

We can generalize the line drawing to handle all 8 octants ...

           Octant  dy < dx
 \  |  /       0   Yes
  \2|1/        1   No
  3\|/0        2   No
 ---+---       3   Yes
  4/|\7        4   Yes
  /5|6\        5   No
 /  |  \       6   No
               7   Yes

... by dividing it into two cases -- if `dy < dx` but this will only work for octants 0 and 1.  Instead we need to look at the absolute value of dy compared to the absolute value of dx.

That is, given:

* Vertex 0: x0, y0
* Vertex 1: x1, y1

We first calculate the deltas, sign of the deltas, and absolute value of the deltas:

```js
    dx = x1 - x0
    dy = y1 - y0

    sx = (dx < 0) ? -1 : +1
    sy = (dy < 0) ? -1 : +1

    ax = Math.abs(dx)
    ay = Math.abs(dy)
```

The slope will tell us which octant we are in  (0 or 1); we do this by inspecting `dy < dx`:

* Yes? Than the slope is < 45°, have octant 0
* No? Than the slope is >= 45°, have octant 1

To generalize this to all octants we use `ay < ax` instead.

* Yes? Than slope is < 45°, we in octants 0, 3, 4, 7,
* No? Than slope is >= 45°, we in octants 1, 2, 5, 6.

We also make use of `sx`, `sy`, `ax`, and `ay` that we calculated above:

```
    if (ay < ax) // < 45 degrees, Octants 0, 3, 4, 7
    {
        e = -ax;
        for( x = 0; x <= ax; ++x )
        {
            setpixel( x0 + x*sx, color )

            e += 2*ay;
            if (e >= 0)
            {
                e -= 2*ax;
                y += sy;
            }
        }
    }
    else // >= 45 degrees, Octants 1, 2, 5, 6
    {
        e = -ay;
        for( y = 0; y <= ay; ++y )
        {
            setpixel( x, y0 + y*sy, color )

            e += 2*ax;
            if (e >= 0)
            {
                e -= 2*ay;
                x += sx;
            }
        }
    }
```

QED.