Алгоритм Брезенхема в JavaScript

Question

Мне нужен быстрый алгоритм для расчета координат для линии между двумя точками. Я пытался найти хорошую реализацию JavaScript в Брезенхеме, но есть слишком много и довольно запутанных публикаций. В википедии - здесь самая быстрая и простая форма (без делений и вычисления ошибок для обоих направлений) представлена ​​в псевдокоде следующим образом:

 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

Знаете ли вы о простой и надежной реализации JavaScript Bresenham, основанной на этом псевдокоде?

РЕДАКТИРОВАТЬ

Спасибо всем! Это то, с чем я пришел в конце:

  function calcStraightLine (startCoordinates, endCoordinates) {
    var coordinatesArray = new Array();
    // Translate coordinates
    var x1 = startCoordinates.left;
    var y1 = startCoordinates.top;
    var x2 = endCoordinates.left;
    var y2 = endCoordinates.top;
    // Define differences and error check
    var dx = Math.abs(x2 - x1);
    var dy = Math.abs(y2 - y1);
    var sx = (x1 < x2) ? 1 : -1;
    var sy = (y1 < y2) ? 1 : -1;
    var err = dx - dy;
    // Set first coordinates
    coordinatesArray.push(new Coordinates(y1, x1));
    // Main loop
    while (!((x1 == x2) && (y1 == y2))) {
      var e2 = err << 1;
      if (e2 > -dy) {
        err -= dy;
        x1 += sx;
      }
      if (e2 < dx) {
        err += dx;
        y1 += sy;
      }
      // Set coordinates
      coordinatesArray.push(new Coordinates(y1, x1));
    }
    // Return the result
    return coordinatesArray;
  }

Answer 1

Переписав ваш псевдокод в JavaScript:

function line(x0, y0, x1, y1){
   var dx = Math.abs(x1-x0);
   var dy = Math.abs(y1-y0);
   var sx = (x0 < x1) ? 1 : -1;
   var sy = (y0 < y1) ? 1 : -1;
   var err = dx-dy;

   while(true){
     setPixel(x0,y0);  // Do what you need to for this

     if ((x0==x1) && (y0==y1)) break;
     var e2 = 2*err;
     if (e2 >-dy){ err -= dy; x0  += sx; }
     if (e2 < dx){ err += dx; y0  += sy; }
   }
}

Обратите внимание, что прямое сравнение чисел с плавающей точкой может закончиться неудачей (хотя это не должно происходить при пошаговом выполнении целых чисел, это может произойти, если конечная точка не является целочисленной), поэтому вместо непосредственного сравнения конечных точек вы можете использовать эпсилон:

if (Math.abs(x0-x1)<0.0001 && Math.abs(y0-y1)<0.0001) break;

Однако это обязательно замедлит вас, поэтому делайте это, только если вы имеете дело с нецелыми числами.

Answer 2

_{Отказ от ответственности: я извлек этот ответ из вопроса ОП. Ответы не должны содержаться в самом вопросе.}

---

Ответ предоставлен Boris Hamanov:

Спасибо всем! Это то, с чем я пришел в конце:

function calcStraightLine (startCoordinates, endCoordinates) {
    var coordinatesArray = new Array();
    // Translate coordinates
    var x1 = startCoordinates.left;
    var y1 = startCoordinates.top;
    var x2 = endCoordinates.left;
    var y2 = endCoordinates.top;
    // Define differences and error check
    var dx = Math.abs(x2 - x1);
    var dy = Math.abs(y2 - y1);
    var sx = (x1 < x2) ? 1 : -1;
    var sy = (y1 < y2) ? 1 : -1;
    var err = dx - dy;
    // Set first coordinates
    coordinatesArray.push(new Coordinates(y1, x1));
    // Main loop
    while (!((x1 == x2) && (y1 == y2))) {
        var e2 = err << 1;
        if (e2 > -dy) {
            err -= dy;
            x1 += sx;
        }
        if (e2 < dx) {
            err += dx;
            y1 += sy;
        }
        // Set coordinates
        coordinatesArray.push(new Coordinates(y1, x1));
    }
    // Return the result
    return coordinatesArray;
}

Answer 3

Я искал ту же самую вещь, и недавно наткнулся на эту интерактивную реализацию алгоритма линии Брезенхема в javascript - перемещайте мышь, чтобы также перемещать линию. Вид аккуратный, чтобы увидеть его в действии, а не просто исходный код алгоритма. Аккуратное объяснение тоже.