绘制4连线的算法

Question

我正在寻找一种算法(用Java编码会很好,但是任何足够清晰的转换为Java都很好)来绘制一条4连接线.似乎Bresenham的算法是使用最广泛的算法,但我发现的所有可理解的实现都是8连接的.OpenCV的cvline函数显然有一个4连接版本,但对我来说,源代码是一个平庸而且几乎是C文盲的程序员,难以理解.其他各种搜索都没有发现.

感谢任何人都能提供的帮助.

Answer 1

以下是类似Bresenham的算法,它绘制了4条连线.代码是用Python编写的,但我想即使你不懂语言也可以轻松理解.

def line(x0, y0, x1, y1, color):
    dx = abs(x1 - x0)    # distance to travel in X
    dy = abs(y1 - y0)    # distance to travel in Y

    if x0 < x1:
        ix = 1           # x will increase at each step
    else:
        ix = -1          # x will decrease at each step

    if y0 < y1:
        iy = 1           # y will increase at each step
    else:
        iy = -1          # y will decrease at each step

    e = 0                # Current error 

    for i in range(dx + dy):
        draw_pixel(x0, y0, color)
        e1 = e + dy
        e2 = e - dx
        if abs(e1) < abs(e2):
            # Error will be smaller moving on X
            x0 += ix
            e = e1
        else:
            # Error will be smaller moving on Y
            y0 += iy
            e = e2

我们的想法是,要画一条线,你应该增加X和Y,其比例与理论线的DX/DY相匹配.为了做到这一点,我从一个初始化为0 的错误变量e(我们在线)开始,在每一步我检查错误是否更低,如果我只增加X或我只增加Y(Bresenham检查是在更改之间选择只有X或X和Y两者).

用于执行此检查的简单版本将添加1/dy或者1/dx,但是将所有增量乘以dx*dy允许仅使用整数值并且提高速度和准确性并且还避免需要特殊情况dx==0或dy==0因此简化逻辑.当然,因为我们正在寻找比例误差,所以使用缩放的增量不会影响结果.

无论线象限是什么,增量的两种可能性总是会对误差产生不同的符号效应...所以我的任意选择是增加X步的误差并减小Y步的误差.

的ix和iy的变量是所需要的线(+1或-1),这取决于所述初始坐标是否比最终坐标更低或更高的实际方向.

在4连接线中绘制的像素数量显然dx+dy是这样的,所以我只需要多次循环来绘制线而不是检查我是否到达终点.请注意,此算法绘制除最后一个像素之外的所有像素; 如果你还需要最后一个像素,那么draw_pixel应该在循环结束后添加一个额外的调用.

在下面的图片中可以看到上述实现的示例结果

Answer 2

对于Python-illiterate,这里是6502代码的C版本:

void drawLine(int x0, int y0, int x1, int y1) {
    int dx = abs(x1 - x0);
    int dy = abs(y1 - y0);
    int sgnX = x0 < x1 ? 1 : -1;
    int sgnY = y0 < y1 ? 1 : -1;
    int e = 0;
    for (int i=0; i < dx+dy; i++) {
        drawPixel(x0, y0);
        int e1 = e + dy;
        int e2 = e - dx;
        if (abs(e1) < abs(e2)) {
            x0 += sgnX;
            e = e1;
        } else {
            y0 += sgnY;
            e = e2;
        }
    }
}