graphics - 绘制四连线的算法

Question

我正在寻找一种算法（用 Java 编码会很好，但任何足够清晰可以转换为 Java 的东西都可以）来绘制一条 4 连接线。似乎Bresenham 的算法是使用最广泛的，但我发现的所有可以理解的实现都是 8 连接的。OpenCV 的cvline函数显然有一个 4-connected 版本，但源代码对我来说，作为一个平庸且近乎 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

这个想法是，要绘制一条线，您应该使用与理论线的 DX/DY 匹配的比率来增加 X 和 Y。为此，我从一个初始化为 0 的错误变量开始e（我们在线上），并且在每一步我检查如果我只增加 X 或如果我只增加 Y（Bresenham 检查是在改变仅 X 或 X 和 Y）。

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

无论行象限是什么，增量的两种可能性总是会对误差产生不同的符号影响......所以我的任意选择是增加 X 步的误差并减少 Y 步的误差。

ix和变量是线所需的iy实际方向（+1 或 -1），具体取决于初始坐标是低于还是高于最终坐标。

显然dx+dy，要在 4 连接线上绘制的像素数是 ，所以我只是做了多次循环来绘制线，而不是检查是否到达终点。请注意，此算法会绘制除最后一个像素以外的所有像素；draw_pixel如果您还想要最后一个像素，则应在循环结束后添加一个额外的调用。

上述实现的示例结果如下图所示

Answer 2

对于 Python 文盲，这里是 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;
        }
    }
}