Javascript 中的 Bresenham 算法 [英] Bresenham algorithm in Javascript
问题描述
我需要一种快速算法来计算两点之间的直线坐标.我试图找到好的 JavaScript Bresenham 实现,但是有太多且令人困惑的出版物.在维基百科 - 这里 最快和最简单的形式(没有除法和两个方向的误差计算) 以这样的伪代码表示:
I need a fast algorithm for calculating coordinates for a line between two points. I tried to find good JavaScript Bresenham implementation, but there are too many and quite confusing publications. In wikipedia - here the fastest and most simple form (no divisions and error calculation for both directions) is presented in pseudocode like this:
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 实现吗?
Do you know of a simple and robust JavaScript Bresenham implementation based on this pseudocode?
推荐答案
将您提供的伪代码重写为 JavaScript:
Rewriting your supplied pseudo-code into 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:
Note that comparing floats directly may fail as you step (though it shouldn't when stepping by integer amounts, it might if either end point is non-integer), so instead of directly comparing the end points you might want to use an epsilon:
if (Math.abs(x0 - x1) < 0.0001 && Math.abs(y0 - y1) < 0.0001) break;
然而,这必然会减慢您的速度,因此只有在您处理非整数时才这样做.
This will necessarily slow you down, however, so only do this if you are dealing with non-integers.
这篇关于Javascript 中的 Bresenham 算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!