Bresenham的线算法所有情况下

Question

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

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

看这里：https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm#All_cases
我试图弄清楚如何改变我的功能，因此它“绘制”一条线在2D矢量任何2个坐标，但我有点困惑。我不明白为什么有一个函数应用于输入和输出。以及哪一个适用于哪个坐标。另外，我不知道如何找出哪个八分圆线从2个坐标是

二维向量将被写入.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），它们在两个不同的八分区中，但在下一节中他们说它只在第一个八分区中工作。