De Casteljau's algorithm to draw Bezier Curves in OOP and C++ (iterative version)

Question

#include <iostream>
#include "Point2d.h"
#include "Collection.h"
#include "Coordinates2d.h"
#include "graphics.h"    

#define PRECISION 0.01

Point2d Approximate(double t, Point2d const & pt1, Point2d const & pt2)
{
    double x = pt1.x * (1-t) + pt2.x * t;
    double y = pt1.y * (1-t) + pt2.y * t;

    return Point2d(x, y);
}

Collection<Point2d> GetBezierPoints(Collection<Point2d> const & points)
{
    Collection<Point2d> bezierPoints;

    for(double t = 0 ; t < 1 ; t = t + PRECISION)
    {
        Collection<Point2d> temp1 = points;

        while(temp1.size()>1)
        {
            Collection<Point2d> temp2;

            for(int i = 0 ; i<temp1.size()-1 ; i++)
            {
                Point2d pt1 = temp1[i];
                Point2d pt2 = temp1[i+1];

                temp2.Add(Approximate(t, pt1, pt2));
            }

            temp1 = temp2;
        }

        bezierPoints.Add(temp1[0]);//finally only one point will be left
    }

    return bezierPoints;
}

int main()
{
    Coordinates2d::ShowWindow("De Casteljau's algorithm");

    Collection<Point2d> points;

    points.Add(Point2d(0,0));
    points.Add(Point2d(80,300));    
    points.Add(Point2d(120,-150));
    points.Add(Point2d(200,0));


    Collection<Point2d> list = GetBezierPoints(points);

    Coordinates2d::Draw(list);

    Coordinates2d::Wait();

    return 0;
}

NOTE: I am in love with my Collection<T> class, which is a wrapper around std::vector.

Answer 1

I am repeating much of what is already in the comments but felt it should be spelled out more explicitly.

Avoid using #define statements

Per Scott Meyers's Effective C++ you should always prefer const to #define statements because #define statements are a preprocessor step, which means when you are debugging, you will see a number and not a variable name. This can make your life very difficult, so you should avoid #defines whenever possible.

Descriptive Naming

You should only use a name like temp when it's really important to emphasize that you are using a temporary variable (say to draw your reader/client's attention to the fact that a function creates a temp object and so should be used sparingly when certain memory concerns are present). Quite literally any other name would be better than temp possibly even var. Why not use pointCollection or something similarly descriptive?

Comments where helpful

I don't see any comments in your code. I am also not familiar with the libraries you are using. If you want a reader like me to understand your code, you should put in some clarification, succinct one line statements should be enough. Even for yourself, you should put in a note about what you hoped to accomplish in a function.

Answer 2

I agree with what others have said regarding naming, constants, and comments.

Are you at all concerned with performance with this code? I ask because copying an entire collection like you do here:

temp1 = temp2;

is likely to be very slow as you do it more often or increase the number of points. (Right now you've got it at 100 points per curve, but if you ever make it more, you'll likely hit performance problems.) Perhaps you could have a couple of intermediate collections and switch back and forth between them using references? (You'd have to keep track of the size rather than relying on the collection to give it you, though.)

Telling us you're in love with your Collection<T> is great, but you should explain what it gets you that using a standard collection doesn't.

A more idiomatic way of using collections in C++ is to use iterators. Instead of getting the size and counting from 0 to size - 1, you can just start iterating.

The t argument to Approximate() should also be const, since it doesn't change.

Answer 3

The names t temp1 and temp2, can surely be improved.

Using += in the loop signature is more common and obvious at first glance.

Handling the last point manually seems hackish, maybe you can just change the loop to run one iteration more.

Answer 4

I liked this sample. I tried to modernize the c++ and to lower the amount of allocation. I also removed all none std includes and tried to find replacements for them.

Here is my modified code:

#include <iostream> // for std::out
#include <vector> // for the points vector
#include <valarray> // for Point2d


using Real = double; // better define Real and not just use double

// A way to have Point2d from an existing std include
// good for job interviews or samples like this one that are shared
using Point2d = std::valarray<Real>;

// a vector of points
using Point2dVec = std::vector<Point2d>;

const Point2d Approximate(const Real t, const Real oneMinusT, const Point2d& pt1, const Point2d& pt2)
{
    return pt1 * oneMinusT + pt2 * t;
}

void GetBezierPoints(Point2dVec const& inputPoints, const Real precision, Point2dVec & resultBezierPoints)
{
    // result
    resultBezierPoints.reserve(static_cast<size_t>(1 / precision + 1));
    resultBezierPoints.clear();

    // temp vector, declare and reserve it here (and not inside the loop) to save allocations
    Point2dVec approximatedPoints;
    approximatedPoints.reserve(inputPoints.size());

    // loop t by precision
    for (Real t = 0; t < 1; t += precision)
    {
        // save (1 - t) now as it is used inside Approximate
        Real oneMinusT = (1 - t);

        approximatedPoints = inputPoints;

        while (approximatedPoints.size() > 1)
        {           
            auto pointsIter = approximatedPoints.begin();

            // as we advance the iter inside the loop and use the next value
            // we loop until the prev to the last item on the list
            auto pointsIterEnd = std::prev(approximatedPoints.end()); 

            // loop using an iterator
            while (pointsIter != pointsIterEnd)
            {
                // save the current iter - Approximate result will be stored here
                // this way we can use a single buffer
                auto updateThisIter = pointsIter; 

                // Approximate the current and next points
                const auto& pt1 = *(pointsIter++);
                const auto& pt2 = *(pointsIter);
                const auto approximatedPoint = Approximate(t, oneMinusT, pt1, pt2);

                // store Approximate result in the same buffer
                *updateThisIter = approximatedPoint;
            }

            approximatedPoints.pop_back();
        }

        //finally only one point will be left
        resultBezierPoints.push_back(approximatedPoints[0]);
    }
}


// an output you can just copy and view in desmos
// https://www.desmos.com/calculator
void OutputForDesmos(Point2dVec const& points)
{
    for (auto& curPoint : points)
    {
        std::cout << curPoint[0] << "," << curPoint[1] << "\n";
    }
}


int main()
{
    Point2dVec points;

    points.push_back({ 0, 0 });
    points.push_back({ 80, 300 });
    points.push_back({ 120, -150 });
    points.push_back({ 200, 0 });

    Point2dVec resultBezierPoints;
    GetBezierPoints(points, 0.01, resultBezierPoints);

    OutputForDesmos(resultBezierPoints);

    return 0;
}

Here is the way I viewed the points online: https://www.desmos.com/calculator/2kk870m7cz