绘制4连线的算法 [英] Algorithm for drawing a 4-connected line

问题描述

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

I'm looking for an algorithm (coded in Java would be nice, but anything clear enough to translate to Java is fine) to draw a 4-connected line. It seems that Bresenham's algorithm is the most widely used, but all the understandable implementations I've found are 8-connected. OpenCV's cvline function apparently has a 4-connected version, but the source code is, to me, as a mediocre and nearly C-illiterate programmer, impenetrable. Various other searches have turned up nothing.

感谢任何人可以提供的任何帮助.

Thanks for any help anyone can provide.

推荐答案

以下是绘制 4 个连通线的类 Bresenham 算法.代码是用 Python 写的，但我想即使你不知道这门语言也很容易理解.

The following is a Bresenham-like algorithm that draws 4-connected lines. The code is in Python but I suppose can be understood easily even if you don't know the language.

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 的 error 变量 e 开始(我们在线上)，并且在每一步我检查错误是否较低，如果我只增加X 或者如果我只增加 Y(Bresenham 检查是选择只改变 X 还是同时改变 X 和 Y).

The idea is that to draw a line you should increment X and Y with a ratio that matches DX/DY of the theoretic line. To do this I start with an error variable e initialized to 0 (we're on the line) and at each step I check if the error is lower if I only increment X or if I only increment Y (Bresenham check is to choose between changing only X or both X and Y).

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

The naive version for doing this check would be adding 1/dy or 1/dx, but multiplying all increments by dx*dy allows using only integer values and that improves both speed and accuracy and also avoids the need of special cases for dx==0 or dy==0 thus simplifying the logic. Of course since we're looking for a proportion error, using a scaled increment doesn't affect the result.

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

Whatever is the line quadrant the two possibilities for the increment will always have a different sign effect on the error... so my arbitrary choice was to increment the error for an X step and decrement the error for an Y step.

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

The ix and iy variables are the real directions needed for the line (either +1 or -1) depending on whether the initial coordinates are lower or higher than the final coordinates.

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

The number of pixels to draw in a 4-connected line is obviously dx+dy, so I just do a loop for that many times to draw the line instead of checking if I got to the end point. Note that this algorithm draws all pixels except the last one; if you want also that final pixel then an extra draw_pixel call should be added after the end of the loop.

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

An example result of the above implementation can be seen in the following picture

这篇关于绘制4连线的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！