A Bresenham Counter Implementation

This "Bresenham Counter" implementation uses the Bresenham line drawing algorithm to obtain N evenly distributed integer values from the integer range [0,R] using simple integer arithmetic (no multiply/divide or floating point each iteration). 

After performing some rather unscientific tests on my laptop I have found this implementation to be 3.75 times faster than performing an integer multiplication/division each iteration and 6.75 times faster then doing a floating point (double) addition and integer conversion each iteration.  DISCLAIMER: Performance gains (if any) will vary from platform to platform.

Here is the implementation:

template <typename T>
class bresenham_counter
{
    /* operator T() returns x[0..N-1] = 0 .. R, i.e. x[n] = (R / (N-1)) * n, without
    using floating point or multiplication/division each iteration */
public:
    bresenham_counter(T range, T number) :
        dx(number-1),
        dy(dx > 0 ? range % dx : 0),
        d(2*dy - dx), incrE(2*dy), incrNE(2*(dy-dx)),
        incrCounter(dx > 0 ? range / dx : 0),
        incrCounterPlus1(dx > 0 ? incrCounter+1 : 0),
        counter(0) {}
    operator T()
    {
        if (d <= 0)
        {
            d += incrE;
            T v = counter;
            counter += incrCounter;
            return v;
        }
        else
        {
            d += incrNE;
            T v = counter;
            counter += incrCounterPlus1;
            return v;
        }
    }
private:
    T dx, dy, d, incrE, incrNE;
    T incrCounter;
    T incrCounterPlus1;
    T counter;
};

Here is an example of usage:

int main()
{
    /* output 10 values from the range 0 to 255 */
    bresenham_counter<int> bc(255, 10);
    for (int i = 0; i < 10; ++i)
    {
        int value = bc;
        std::cout << value << std::endl;
    }
    return 0;
}

The output of which is:

0
28
57
85
113
142
170
198
227
255

To support the more general range [Q,R] where Q and R can be positive or negative and/or R < Q simply add the following constructor to the above implementation:

    bresenham_counter(T rangeStart, T rangeEnd, T number) :
        dx(number-1),
        dy(dx > 0 ? rangeEnd > rangeStart ?
            (rangeEnd - rangeStart) % dx : (rangeStart - rangeEnd) % dx : 0),
        d(2*dy - dx), incrE(2*dy), incrNE(2*(dy-dx)),
        incrCounter(dx > 0 ? (rangeEnd - rangeStart) / dx : 0),
        incrCounterPlus1(dx > 0 ? rangeEnd > rangeStart ?
            incrCounter+1 : incrCounter-1 : 0),
        counter(rangeStart) {}

Here is an example of usage:

int main()
{
    /* output 16 values from the range 7 to -42 */
    bresenham_counter<int> bc(7, -42, 16);
    for (int i = 0; i < 16; ++i)
    {
        int value = bc;
        std::cout << value << std::endl;
    }
    return 0;
}

The output of which is:

7
4
0
-3
-6
-9
-13
-16
-19
-22
-26
-29
-32
-35
-39
-42

Click here for an alternative implementation which is easier on the eyes but slightly slower than this implementation due to the presence of an extra subtraction.


You can e-mail comments to the author.

Back to project page