This is an implementation of the Bresenham line drawing algorithm. The program is based on 3 classes, vertex, line and grid. I wrote it with a view to future expansion, so it makes use of templates and flexible STL structures.
The program loads the line data from the input file. The two example lines are already saved there for demonstation. The lines are drawn on a 20*10 grid. Coordinates start from 0. Out-of-bounds coords will not be accepted by the program.
The full source code, with visual studio 2010 project files, is available HERE.
There are many implementations of the algorithm on the web, but one more example can't hurt. Bear in mind this functon uses variables and classes implimented elsewhere:
//----------------------------------------------------------------
// Bresenham line algorithm
void line::fillPixels()
{
int numPixels;
int numerator;
int denominator;
int numeratorInc;
int X_incrementOne;
int X_incrementTwo;
int Y_incrementOne;
int Y_incrementTwo;
vertex currentPixel = m_pointOne;
//Find the absolute difference between the two points
int deltaX = abs(m_pointTwo.getX() - m_pointOne.getX());
int deltaY = abs(m_pointTwo.getY() - m_pointOne.getY());
// If the X values are equal or increasing...
if (m_pointTwo.getX() >= m_pointOne.getX())
{
X_incrementOne = 1; // The line increments positively in X
X_incrementTwo = 1;
}
else // If the X values are decreasing...
{
X_incrementOne = -1; // The line increments negatively in X
X_incrementTwo = -1;
}
// If the Y values are equal or increasing...
if (m_pointTwo.getY() >= m_pointOne.getY())
{
Y_incrementOne = 1; // The line increments positively in Y
Y_incrementTwo = 1;
}
else // If the Y values are decreasing...
{
Y_incrementOne = -1; // The line increments negatively in Y
Y_incrementTwo = -1;
}
if (deltaX >= deltaY) // If rate of change in X is greater than in Y
{
X_incrementOne = 0; // Hold X steady when numerator >= denominator, increment on loop
Y_incrementTwo = 0; // Hold Y steady when for every iteration, increment when numerator >= denominator
denominator = deltaX; // Define the fraction
numerator = deltaX / 2;
numeratorInc = deltaY; // Amount the numerator increases each loop
numPixels = deltaX; // Let delta X define the number of iterations
}
else // If rate of change in Y is greater than in X
{
X_incrementTwo = 0; // Hold X steady when for every iteration, increment when numerator >= denominator
Y_incrementOne = 0; // Hold Y steady when numerator >= denominator, increment on loop
denominator = deltaY; // Define the fraction
numerator = deltaY / 2;
numeratorInc = deltaX; // Amount the numerator increases each loop
numPixels = deltaY; // Let delta Y define the number of iterations
}
// Execute the loop to define pixels
for (int i = 0; i <= numPixels; i++)
{
m_pixels.push_back(currentPixel); // Add the current pixel to the list
numerator += numeratorInc; // Increase the numerator by the top of the fraction
if (numerator >= denominator) // Check if numerator >= denominator
{
numerator -= denominator; // Set the new numerator value
currentPixel.incrementVertex(X_incrementOne,0); // Increment x
currentPixel.incrementVertex(0,Y_incrementOne); // Increment y
}
currentPixel.incrementVertex(X_incrementTwo,0); // Increment x
currentPixel.incrementVertex(0,Y_incrementTwo); // Increment y
}
}