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

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

}

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;

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.

• It looks good to me. The only thing I would change right now is that PRECISION constant, which would be better as a const double to give it an actual type. Aug 10, 2015 at 19:09
• What is so good about your Collection<> that you would want to use it over a std::vector<>? Jul 25, 2020 at 15:51

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?

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.

• Adding to the first point, const carry more, and especially more consistent type information than #define. Jul 25, 2020 at 17:03

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.

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.

• += is corrected.
– user3804
Aug 10, 2015 at 16:02
• But, i could not figure out your suggestion about temp1[0].
– user3804
Aug 10, 2015 at 16:18
• @anonymous Dont modify code in question. About the loop I mean using <= instead of < but it is not tested Aug 10, 2015 at 16:33
• even if i use <=, how would it help to remove the manual handling of the last point?Please, You can show me.
– user3804
Aug 10, 2015 at 16:36
• @anonymous Sorry I have no idea, I was just thinking out loud :) Aug 10, 2015 at 16:41

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

• Complex numbers are not equivalent to 2D coordinates. Some operations on complex numbers don't do what you would expect. I would suggest using std::valarray instead, or types from a proper vector math library. Jul 25, 2020 at 15:50
• Thanks G. Sliepen, I agree. I switched to std::valarray as you suggested. Jul 25, 2020 at 16:45
• Switched to using a single buffer. Jul 26, 2020 at 9:42