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），它們在兩個不同的八分區中，但在下一節中他們說它只在第一個八分區中工作。