Ho bisogno di un algoritmo veloce per calcolare le coordinate di una linea tra due punti. Ho cercato di trovare una buona implementazione JavaScript di Bresenham, ma ci sono troppe pubblicazioni abbastanza confuse. In wikipedia - here la forma più veloce e più semplice (senza divisioni e il calcolo degli errori per entrambe le direzioni) è presentato in pseudocodice come questo:Algoritmo di Bresenham in 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
Sapete di un'implementazione semplice e robusto JavaScript Bresenham sulla base di questo pseudocodice?
EDIT
Grazie a tutti! Questo è quello che mi è venuto con alla fine:
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;
}
Brasenham dovrebbe funzionare comunque solo su interi. È usato per calcolare quali pixel colorare disegnare una linea. –
Mi piace questo, ma penso che possa essere ulteriormente migliorato rimuovendo l'interruzione a favore della condizione del loop reale e facendo la moltiplicazione per due con shift. –
Lo spostamento di bit potrebbe essere più veloce, ma dubito che la modifica del ciclo influenzi le prestazioni. Puoi facilmente cambiarlo in 'while (x0! = X1 || y0! = Y1)' e rimuovere 'if/break', ma dovresti estrarre un'altra chiamata a' setPixel' prima/dopo il ciclo da gestire il punto finale della linea correttamente e il caso limite. – Phrogz