c++ - Bresenham 的线算法所有情况

Question

我创建了一个函数，它接受一个 2D std::vector， vector 中的 2 个点，并在 vector 中“绘制”一条线。但是，它并不涵盖所有情况(八分圆)。一条线是指在一条直线上相互连接的点。该 vector 将写入 .ppm 文件，因此它在图像中显示为一条线。

我使用此链接实现了此功能:https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

看这里:https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm#All_cases
我试图弄清楚如何更改我的函数，以便它为 2D vector 中的任意 2 个坐标“绘制”一条线，但我有点困惑。我不明白为什么有一个函数可以应用于输入和输出。以及在哪个坐标上应用哪个。另外，我不知道如何找出来自 2 个坐标的线在哪个八分圆中。

2D vector 将被写入 .ppm 文件，如下所示:

255 255 255  255 255 255  255 255 255
255 255 255  0 0 0  255 255 255
255 255 255  255 255 255  255 255 255

这张图片的中心是一个黑点。

#include <vector>
#include <tuple>
#include <utility>

using pixel  = std::tuple<unsigned, unsigned, unsigned>; // rgb pixel
using row_t  = std::vector<pixel>; // row in a 2D vector
using grid_t = std::vector<row_t>; // the grid made up of rows
// x, y coordinate - access is like grid[y][x] since grid is made of rows
using coord  = std::pair<long long, long long>;

// Bresenham's line algorithm
// 2 points to draw a line between
void draw(grid_t& grid, const coord& c1, const coord& c2)
{
    long long dx{c2.first - c1.first},
              dy{c2.second - c1.second},
              D {2 * dy - dx},
              y {c1.second};
    // is the if/else needed?
    if (c1.first <= c2.first)
        for (long long x{c1.first}; x <= c2.first; ++x)
        {
            grid[y][x] = pixel{0, 0, 0};
            if (D > 0)
            {
                ++y;
                D -= 2 * dx;
            }
            D += 2 * dy;
        }
    else
        for (long long x{c1.first}; x >= c2.first; --x)
        {
            grid[y][x] = pixel{0, 0, 0};
            if (D > 0)
            {
                ++y;
                D -= 2 * dx;
            }
            D += 2 * dy;
        }
}

任何帮助使此功能适用于所有情况(以及如何使其变得更好)并帮助我理解将不胜感激。

Answer 1

输入函数转换坐标，使得转换后它们始终位于第一个八分圆。应用该算法(仅适用于第一个八分圆)后，您必须再次将它们转换回原始八分圆。

使用了这个技巧，因为每个八分圆的算法都需要不同。不是为所有不同的情况编写代码，而是应用转换以使算法本身保持简单。

但是，我也不完全理解如何正确应用该转换。维基百科文章对此不是很清楚。在他们的示例中，他们有 (0, 1), (6, 4)，它们位于两个不同的八分圆中，但在下一节中他们说它仅适用于第一个八分圆。