39

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

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

4

2 回答 2

62

将您提供的伪代码重写为 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; }
   }
}

请注意，直接比较浮点数可能会在您步进时失败（尽管它不应该在步进整数时失败，如果任一端点都是非整数则可能），因此您可能希望使用 epsilon 来代替直接比较端点：

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

但是，这必然会减慢您的速度，因此只有在处理非整数时才这样做。

于 2011-01-12T18:12:15.513 回答
5

免责声明：我从 OPs 问题中提取了这个答案。答案不应包含在问题本身中。

鲍里斯·哈马诺夫提供的答案：

谢谢大家！这是我最后带来的：

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;
}
于 2019-04-13T14:25:12.470 回答