Алгоритм Брешенема в Javascript

Мне нужен быстрый алгоритм для расчета координат для линии между двумя точками. Я пытался найти хорошую реализацию 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, основанной на этом псевдокоде?

Ответ 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;

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

Ответ 2

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

Ответ 3

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

Ответ предоставлен Борисом Гамановым:

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

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;
}