Multi-Dimensional Bresenham Line in C++

Implementation of a multi-dimensional Bresenham Line algorithm in C++ using STL.

#include <vector>

/**
  Multi-dimenstional Bresenham line algorithm
*/
std::vector< std::vector <int> >
Bresenham(std::vector<int> &from, std::vector<int> &to)
{
  std::vector<int> current;
  for (size_t i=0; i<from.size(); i++)
    current.push_back(from[i]);

  std::vector<int> diff;
  for (size_t i=0; i<from.size(); i++)
    diff.push_back(to[i] - from[i]);

  int num_steps = 0;
  for (size_t i=0; i<diff.size(); i++)
    num_steps = std::max(num_steps, (int)floor(std::abs(diff[i])));

  std::vector<int> step;
  for (size_t i=0; i<diff.size(); i++)
    step.push_back(diff[i]/num_steps);

  std::vector< std::vector <int> > output;
  for (int i=0; i<num_steps; i++)
  {
    std::vector pt;

    for (size_t j=0; j<current.size(); j++)
      pt.push_back(floor(current[j]));

    output.push_back(pt);

    for (size_t j=0; j<current.size(); j++)
      current[j] = current[j] + step[j];
  }
  return output;
}

Leave a comment