Алгоритм Брезенхема в JavaScript - PullRequest
Новая
       51

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

28 голосов
/ 12 января 2011

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

Ответы [ 2 ]

48 голосов
/ 12 января 2011

Переписав ваш предоставленный псевдокод в 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;

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

1 голос
/ 13 апреля 2019

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

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

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

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