使用Javascript中的Bresenhamalgorithm

我需要一个快速algorithm来计算两点之间的直线坐标。 我试图find好的JavaScript Bresenham实现，但是有太多而且相当混乱的出版物。 在维基百科 – 这里最快和最简单的forms（没有两个方向的分割和误差计算）以伪代码的forms呈现，如下所示：

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实现吗？

编辑

谢谢大家！ 这是我最后的结果：

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

请注意，直接比较浮点数可能会失败（尽pipe不应跨步整数时，如果两个端点之一不是整数），所以不要直接比较可能要使用epsilon的端点：

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

这样会减慢你的速度，所以只有在处理非整数时才这样做。