Алгоритм Bresenham в Javascript

Question

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

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 на основе этого псевдокода?

EDIT

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

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; 

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