Bresenham线绘制实现

Question

我发现自己不得不实现Bresenham的直线绘制算法。

我正在寻找关于有效性和代码风格的反馈。我能以某种方式减少代码吗？

template<typename Callable>
void bresenham(Vec2i p0, Vec2i p1, Callable&& cb){
    const auto swap_xy = std::abs(p1.y - p0.y) > std::abs(p1.x - p0.x);
    if (swap_xy) {
        swap(p0.x, p0.y);
        swap(p1.x, p1.y);
    }

    auto mark = [swap_xy, &cb](Vec2i p) {
        if (swap_xy) {
            cb(Vec2i (p.y, p.x));
        }
        else {
            cb(p);
        }
    };

    const auto d = p1 - p0;
    const auto dx_abs = std::abs(d.x);
    const auto step_y = d.y < 0 ? -1 : 1;
    const auto step_x = d.x < 0 ? -1 : 1;
    auto pen = p0;
    while (pen.x != p1.x) {
        bool skip = false;
        auto error = std::abs(2 * d.y*(pen.x - p0.x) - 2 * d.x*(pen.y - p0.y));
        while (error > dx_abs) {
            pen.y += step_y;
            error -= 2 * dx_abs;
            mark(pen);
            skip = true;
        }
        if (!skip) {
            mark(pen);
        }
        pen.x += step_x;
    }
    mark(p1);
}

类Vec2i相当于：

struct Vec2i{
   Vec2i(int ax = 0, int ay = 0) : x(ax), y(ay) {}
   int x,y;
};

使用通常与数学向量相关联的预期复制构造函数和算术运算符。

我已经对此进行了广泛的测试，没有发现任何问题。虽然我有点担心，因为我看到的大多数实现都要长得多(2-3x)，并且对很多情况都有特殊的处理，这些案例似乎只是在我的单元测试中起作用。

我接受任何类型的回调，将被要求为每个产生的立场。有些时候，我需要对这条线进行渲染，有些时候，我只需要沿着这条线迭代并做一些事情。这对我来说是合适的。

Answer 1

听起来不错。我非常喜欢回调机制，它可以对标记的位置做我们想做的任何事情，而不是一个具体的行动。这是一个通用工具；好的设计。对于改进算法本身，我没有什么可说的，但无论如何，这是我的两分钱：

• 你有using std::swap;吗？否则，我不认为对swap的不合格调用将按预期工作。
• 虽然auto是一个很好的工具，但有时我并不认为它增加了可读性。例如，我花了更多的时间才希望看到swap_xy是一个bool。无论如何，这都很容易引起争论，但我认为您永远不会用另一种类型来代替它，而一个显式的bool就会突出它的逻辑。不过，这仍然是主观的。
• 仍然相当主观，但不是这样: auto = p0；but (pen.x != p1.x) { // .X += step_x；}我将使用for循环，因为您显式地具有初始化、条件和步骤。每个人都使用相同的变量pen，这不是在循环之后使用的。for (自动笔= p0；pen.x != p1.x；pen.x += step_x) { // .}
• 再次吹毛求疵，但在计算std::abs时，我会考虑到error中的2倍乘法: auto error =2* std::abs(d.y*(pen.x - p0.x) -d.x*(pen.y-p0.y))；顺便说一下，这个因式分解强调了另一种情况:实际上不需要将乘法2保留在error中；您只需要它来进行比较: auto =std：：abs(d.y*(pen.x-p0.x)-d.x*(pen.y-p0.y))；而(2 * error > dx_abs) { pen.y += step_y；error -= dx_abs；mark(pen)；skip = true；}这并不是说这会产生很大的影响，但它仍然会使代码变得更加简洁。