绘制四连通线的算法

Question

我正在寻找一种算法（最好是用Java编写的，但任何足够清晰以便翻译成Java的东西都可以），用于绘制4连通线。似乎Bresenham算法是最广泛使用的，但我发现所有易懂的实现都是8连通的。OpenCV的cvline函数显然有一个4连通版本，但对我来说，作为一个平庸而几乎不懂C语言的程序员，源代码是无法理解的。各种其他搜索都没有结果。

感谢任何人能提供的帮助。

- elhefe

---

这是cvline的源代码。由于新用户限制，我无法在原始帖子中添加它。 - elhefe

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。为此，我从一个名为“error”的变量e开始初始化为0（我们在直线上），并且在每个步骤中，我检查如果仅递增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调用。

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

- 6502

---

抱歉接受时间这么长，被其他事情占据了。我编写完Java版本后会发布。 - elhefe

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;
        }
    }
}

- Miriam

Answer 3

连接分数坐标的数字直线可能与连接整数坐标的直线不同。 例如，考虑下面的图像，显示了点（1, 1）-（6, 3），（1, 0.6）-（6, 2.6）和（1, 1.4）-（6, 3.4）之间的4连通数字直线。 示例图像 尽管所有起始点和终点都位于像素（1, 1）和（6, 4）上，但数字直线却不同。

下面的代码计算了分数起点和终点之间的4连通数字直线。 实际上，该代码也适用于n维，并计算2n连通的数字直线。

import numpy as np

def points_on_line(start, end):

    idx = np.round(np.array(start)).astype(int)
    end_idx = np.round(np.array(end)).astype(int)
    points = [idx]

    if np.all(idx == end_idx):
        return points

    diff = np.array(end, dtype=float) - np.array(start, dtype=float)
    direction = (diff / np.abs(diff)).astype(int)
    coord = np.array(start, dtype=float)

    while np.any(idx != end_idx):
        # compute how far we need to go to reach the side of the pixel at idx
        t = (idx + direction / 2 - coord) / diff
        i = np.argmin(t)
        coord += t[i] * diff
        idx = idx.copy()
        idx[i] += direction[i]
        points.append(idx)

    return points

- badboul