De Boor’s Algorithm in C++

October 18, 2009

Here is the c++ code for the De Boor algorithm. It calculates a point C(x) on a B-Spline curve of any degree.

Point deBoor(int k,int degree, int i, double x, double* knots, Point *ctrlPoints)
{   // Please see wikipedia page for detail
	// note that the algorithm here kind of traverses in reverse order
	// comapred to that in the wikipedia page
	if( k == 0)
		return ctrlPoints[i];
		double alpha = (x-knots[i])/(knots[i+degree+1-k]-knots[i]);
		return (deBoor(k-1,degree, i-1, x, knots, ctrlPoints)*(1-alpha )+deBoor(k-1,degree, i, x, knots, ctrlPoints)*alpha );

The Point class is defined as the follow:

class Point
	// copy operator
	Point operator=(const Point pt) ;
	Point operator+(const Point pt) const;
	//Point operator-(const Point pt) const;
	Point operator*(double m) const;
	Point operator/(double m) const;
	double x,y,z;

Point Point::operator=(const Point pt)
	x = pt.x;
	y = pt.y;
	z = pt.z;
	return *this;
Point Point::operator+(const Point pt) const
	Point temp;
	temp.x = x + pt.x;
	temp.y = y + pt.y;
	temp.z = z + pt.z;
	return temp;
Point Point::operator*(double m) const
	Point temp;
	temp.x = x*m;
	temp.y = y*m;
	temp.z = z*m;
	return temp;
Point Point::operator/(double m) const
	Point temp;
	temp.x = x/m;
	temp.y = y/m;
	temp.z = z/m;
	return temp;

CGAL Installation guide

February 21, 2008

For Linux (ubuntu)

  1. Install boost. Go to to check the newest version available. The newest version as of feb,2008 is 1.34.1.
  2. Open a terminal and input
    sudo apt-get install libboost.*-dev libboost-doc libboost.*1.34.1
  3. Boost is installed in a standard location and should be found by CGAL installation program automatically.
  4. Download latest CGAL from this link.
  5. Decompress the downloaded file by inputting
    sudo tar xfv CGAL-3.3.1.tar.gz
  6. Go to the directory CGAL-3.3.1 and input ./install_cgal -i. -i for interactive mode.
  7. Input T for testing the setup. After the testing, the boost you just installed should appear on the the support for menu.
  8. Type B to build the CGAL library. If you h sudo apt-get install libmpfr-devave error message, like “Compilation of libCGAL static failed”, check the install.log file. That is probably due to the missing of MPFR or GMP. Below are the commands to install them respectively.
    sudo apt-get install libgmp3-dev

    sudo apt-get install libmpfr-dev

    After you install MPFR or GMP, go to the main menu and input S -> 7 or 5 -> 0 to auto find the library. If library is installed correctly, it should appear on the the support for: on the main menu along with other library like BOOST.
  9. If you prefer to install CGAL into other directory, Press I and then D to change the installation directory to any director you want, for example, /usr/local/CGAL. Then press I again to let the installer to copy all include/lib/exe files to the designated directory.
  10. If you have problem creating directory in step 9. Just exit the installer and input the command
    ./install_cgal –prefix /usr/local/CGAL -i.
    Then under the main men, press I and install root directory defined by the –prefix parameter should be changed to /usr/local/CGAL. You don’t need to press D to change the install root directory again. Simply press I, the installer should work fine and all required files will be copied to the designated directory.
  11. DONE! 🙂