Javascript Midpoint Line Drawing Algorithm

Question

I'm drawing a line in javascript using the Midpoint Algorithm Line Drawing. When the line is in a descent trajectory, it computes the wrong values. Can somebody help me?

data input //midline(1,6,8,4);

function midline(x0, y0, x1, y1) {
  /* Using midpoint algorithm for lines. */
  const dx = x1 - x0;
  const dy = y1 - y0;
  var d = 2 * dy - dx;
  const incrE = 2 * dy;
  const incrNE = 2 * (dy - dx);
  var x = x0;
  var y = y0;

  var output = [];

  //listeners
  console.log("dy = ", dy, "dx = ", dx);
  console.log("d = ", d);
  console.log("incrE = ", incrE);
  console.log("incrNE = ", incrNE);
  console.log("----------------------------------");

  while (x <= x1) {
    // if not the last x
    console.log("x = ", x, " y = ", y);
    output.push([x,y]);


    if (d <= 0) {
      console.log("E");

      d = d + incrE;
      x++;
    } else {
      console.log("NE");

      d = d + incrNE;
      x++;
      y++;
    }
  }
  console.table(output);
}

user_7696162 · Answer

If per my comment the Mid Point Line Drawing algorithm is only suited for the first quadrant, that is...

 x0 < x1 and y0 < y1

...must hold true, then adjustments are required if x1 < x0 or y1 < y0.

Taking the case presented (1,6) - (8,4), this is a downward slope because y1 < y0 (ie, 4 < 6 ). To make this a workable case for the Mid Point Line Drawing algorithm, you can simply negate the y values, in which case y0 < y1 will then hold true. Of course, when capturing the results, the values need to then be adjusted by multiplying by -1 again. So, suggest wedging in the following before putting x0, y0, x1, and y1 to use...

let xReflect = 1;
if ( x1 < x0 ) {
    x0 = -x0;
    x1 = -x1;
    xReflect = -1;
}

let yReflect = 1;
if ( y1 < y0 ) {
    y0 = -y0;
    y1 = -y1;
    yReflect = -1;
}

...and then, when pushing the output to the array, you will need to perform the following...

output.push( [ x * xReflect, y * yReflect ] );

Hope this helps.

Javascript Midpoint Line Drawing Algorithm

1 Answers