39

2 点間の線の座標を計算するための高速なアルゴリズムが必要です。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; }
   }
}

フロートを直接比較すると、ステップとして失敗する可能性があることに注意してください (整数量でステップする場合は失敗するべきではありませんが、いずれかの端点が整数でない場合は失敗する可能性があります)。そのため、端点を直接比較する代わりに、イプシロンを使用することをお勧めします。

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

ただし、これは必然的に速度が低下するため、非整数を扱う場合にのみこれを行ってください。

于 2011-01-12T18:12:15.513 に答える