Bresenham Algorithmus in Javascript

Question

Ich brauche einen schnellen Algorithmus für die Berechnung von Koordinaten für eine Linie zwischen zwei Punkten. Ich habe versucht, eine gute JavaScript-Implementierung von Bresenham zu finden, aber es gibt zu viele und ziemlich verwirrende Veröffentlichungen. In wikipedia - here die schnellste und einfachste Form (ohne Spaltungen und Fehlerberechnung für beide Richtungen) in Pseudo-Code wie folgt dargestellt:

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 

Kennen Sie eine einfache und robuste Implementierung JavaScript Bresenham basierend auf dieser Pseudo-Code?

EDIT

Vielen Dank allen! Dies ist, was ich mit am Ende kam:

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

Ihren gelieferten Pseudo-Code in JavaScript Umschreiben:

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

Beachten Sie, dass Schwimmer kann direkt Vergleich fehlschlagen, wie Sie Schritt (obwohl es nicht sollte, wenn durch ganzzahlige Beträge treten, könnte es, wenn entweder Endpunkt ist nicht ganzzahligen), so, anstatt direkt die Endpunkte zu vergleichen Sie könnten ein epsilon verwenden möchten:

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

Dies wird zwangsläufig verlangsamen Sie aber tue dies nur, wenn du mit nicht-ganzen Zahlen arbeitest.