Javascript 中的 Bresenham 算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4672279/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Bresenham algorithm in Javascript
提问by Boris Hamanov
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 - herethe fastest and most simple form (no divisions and error calculation for both directions) is presented in pseudocode like this:
我需要一个快速算法来计算两点之间的线的坐标。我试图找到好的 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
Do you know of a simple and robust JavaScript Bresenham implementation based on this pseudocode?
你知道一个基于这个伪代码的简单而健壮的 JavaScript Bresenham 实现吗？
回答by Phrogz
Rewriting your supplied pseudo-code into JavaScript:
将您提供的伪代码重写为 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; }
}
}
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:
请注意，直接比较浮点数可能会在您步进时失败（尽管在按整数步进时不应该这样做，如果任一端点是非整数，则可能会失败），因此，您可能想要使用 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.
但是，这必然会减慢您的速度，因此只有在处理非整数时才这样做。
回答by Neuron
Disclaimer: I extracted this answer from the OPs question. Answers should not be contained in the question itself.
免责声明：我从 OPs 问题中提取了这个答案。答案不应包含在问题本身中。
Answer provided by Boris Hamanov:
鲍里斯·哈马诺夫提供的答案：
Thanks everybody! This is what I came with at the end:
谢谢大家！这是我最后带来的：
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;
}
