java - Bresenham 的画线算法的错误

Question

我正在尝试使用 Bresenham's Line Drawing Algorithm在 20x20 的瓷砖网格上画一条线。

所以基本上，当变量 deltaerror(来自 wiki)大于 1(当 y 的变化大于 x 的变化)时，y 值几乎变成它应该的两倍。希望我在代码的注释中更好地解释它。我还认为我找到了错误的根源，我也会在评论中对此进行解释。

这是我做的代码，大部分是从wiki中的伪代码复制过来的。

public static void drawLine(Tile t1, Tile t2) {
    int dx = t2.x_index - t1.x_index;
    int dy = t2.y_index - t1.y_index;
    double error = 0;
    double d_error = Math.abs((double) dy / dx); // dx =/= 0, therefore no vertical lines

    // when d_error is greater than 1, the bug occurs

    int y = t1.y_index;
    if (d_error <= 1) { // if related acute angle is < 45 degrees
        if (dx < 0) { // line drawn towards left side of screen
            for (int x=t1.x_index; x>=t2.x_index; x--) {
                Board.tiles[x][y].setColour(Color.red);
                error += d_error;
                while (error >= 0.5) {
                    Board.tiles[x][y].setColour(Color.red);
                    y += dy > 0 ? +1 : -1;// this is where I think the error occurs. In the 
                                          // wiki for the algorithm, this should be some 
                                          // function sign(T) which "decides whether t is 
                                          // positive or negative". I wasn't really sure 
                                          // what this meant, so I just assumed it returned 
                                          // -1 if it was negative and +1 if it was positive. 
                                          // Also it's the only place where y is edited
                                          // that seems to be where the error is occurring. 
                    error -= 1.0;
                }
            }
        } else if (dx > 0) { // line drawn towards right side of screen
            for (int x=t1.x_index; x<=t2.x_index; x++) {
                Board.tiles[x][y].setColour(Color.red);
                error += d_error;
                while (error >= 0.5) {
                    Board.tiles[x][y].setColour(Color.red);
                    y += dy > 0 ? +1 : -1;
                    error -= 1.0;
                }
            }
        }

    // update: switched x and y values when d_error is greater than 1.

    } else { // if related acute angle is > 45 degrees
        dx = t2.y_index - t1.y_index; // switch x and y values
        dy = t2.x_index - t1.x_index;

        d_error = Math.abs((double) dy / dx); // recalculate d_error
        y = t1.x_index;
        if (dx < 0) { // line drawn towards left side of screen
            for (int x=t1.y_index; x>=t2.y_index; x--) {
                Board.tiles[x][y].setColour(Color.red);
                error += d_error;
                while (error >= 0.5) {
                    Board.tiles[x][y].setColour(Color.red);
                    y += dy > 0 ? +1 : -1;
                    error -= 1.0;
                }
            }
        } else if (dx > 0) { // line drawn towards right side of screen
            for (int x=t1.y_index; x<=t2.y_index; x++) {
                Board.tiles[x][y].setColour(Color.red);
                error += d_error;
                while (error >= 0.5) {
                    Board.tiles[x][y].setColour(Color.red);
                    y += dy > 0 ? +1 : -1;
                    error -= 1.0;
                }
            }
        }
    }
}

感谢您的帮助!

编辑:当 d_error 大于 1 时切换 x 和 y 值。当斜率高于 1 且低于 -1 时，该线消失。

Answer 1

引用快速谷歌结果:

http://www.math.ubc.ca/~cass/courses/m308-02b/projects/puhalovic/#alldirections

“如果斜率大于 1 或小于 -1，我们必须采用之前的实现并交换所有 x 和 y 值以将计算“移动”回“第一八分圆”。”

IOW:bresenham 的教科书实现仅适用于具有(用您的话来说)d_error<=1 的行.您必须实现上面链接中提到的交换。