0

I created a function which takes in a 2D std::vector, 2 points in the vector, and "draws" a line within the vector. But, it doesn't cover all the cases (octants). By a line I mean the points connected to each other in a straight line. This vector will be written to a .ppm file, so it appears as a line in the image.

I implemented this function using this link: https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

Looking here: https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm#All_cases
I tried to figure out how to change my function so it "draws" a line for any 2 coordinates in the 2D vector, but I'm a little confused. I don't understand why there is a function to apply on the input and output. And which one to apply on which coordinate. Also, I don't know how to figure out which octant the line from the 2 coordinates is in.

The 2D vector will be written to the .ppm file like this:

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

This image would be a black dot in the center.

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

Any help in making this function work for all the cases (and how to make it better) and helping me understand how would be appreciated.

cppxor2arr
  • 295
  • 2
  • 12

1 Answers1

2

The function on input transforms the coordinates such that after the transformation they are always in the first octant. After applying the algorithm (that only works for the first octant), you have to transform them back to the original octant again.

The trick is used, because the algorithm would need to be different for each octant. Instead of writing code for all different cases, a transformation is applied such that the algorithm itself stays simple.

However, I also don't fully understand how to apply that transform correctly. The Wikipedia article isn't quite clear on that. In their example, they have (0, 1), (6, 4) which are in two different octants, but in the next section they say it's only working for the first octant.

463035818_is_not_an_ai
  • 109,796
  • 11
  • 89
  • 185
  • Thank you for clarifying. I was a bit hazy after reading the article. Now I just need to figure out how to determine which octant the line that would be created by the 2 coordinate points is in. – cppxor2arr Aug 10 '17 at 09:50
  • Why would you need to transform the coordinates after applying the algorithm? The coordinates would already be plotted (drawn). – cppxor2arr Aug 10 '17 at 09:55
  • @cppxor2arr you have to either transform them before plotting or apply the transform to the whole image i guess. Just think of it like this: You only know how to add positive numbers. If I want you to add -3 to -5 I will ask you to add 3 and 5, you tell me that the answer is 8 and then I still have to apply the inverse transform to get -8 – 463035818_is_not_an_ai Aug 10 '17 at 09:58
  • So, are the 2 ways: **1.** Transform the 2 coordinates before running the algorithm and then run it while plotting points. Transform the whole image by iterating through the elements of the 2D vector, transform each current coordinate, and swap elements of the current coordinate and the transformed current coordinate. **2.** Transform the 2 coordinates before running the algorithm. While running the algorithm store the coordinates to be plotted. Transform the stored coordinates and plot them. Any mistakes? – cppxor2arr Aug 10 '17 at 10:21
  • @cppxor2arr I am also not sure on the details. I will try it at home (but not during working hours ;). Its a quite nice problem, because if you do something wrong you immediately see what went wrong – 463035818_is_not_an_ai Aug 10 '17 at 10:22
  • Yes, just looking at the image generated will show if the logic is right. – cppxor2arr Aug 10 '17 at 10:23
  • I found a working implementation of Bresenham's line algorithm in `C#` here: https://stackoverflow.com/a/11683720/6877265. After translating it to C++ I tested it a lot and so far it seems to work pretty good. Though I still don't understand it. – cppxor2arr Aug 11 '17 at 06:21