Geometrie/Algoritmus de Boor

De Boor algoritmus

editovat

De Boor algoritmus pro výpočet bodu B-spline křivky je zobecněním algoritmu de Casteljau pro Bézierovy křivky. Pro   vypočítáme bod na B-spline křivce opakovanou lineární interpolací:

 ,

kde

  a  .

Bod   je hledaný bod na B-spline křivce.

Algoritmizace

editovat

ComputeKnotVector(int n, int k)

editovat

Spočítá uzlový vektor.

Parametry:

  • n - počet kontrolních bodů mínus 1
  • k - stupeň de Boor bázové funkce
void ComputeKnotVector(int n, int k)
 {
  parametrization = new ParameterCollection();
  for(int i=0; i<=n+k+1; i++)
  {
   if(i<=k) parametrization.Insert(i,0);
    else
   if(i>n) parametrization.Insert(i,n-k+1);
    else
   parametrization.Insert(i,i-k);
  }
 }

Vector GetPoint(double t)

editovat

Přetížená metoda třídy Curve. Spočítá a vrátí bod na křivce.

Parametry:

  • t - parametr výpočtu
public override Vector GetPoint(double t)
 {
  ParameterCollection u = parametrization;
  int n = ctrlPoly.Count;
  Vector[] points = new Vector[n];
  for (int i=0;i<n;i++)
  {
   points[i] = ((RichPoint)(ctrlPoly[i])).Locate;
  }
  int l=0;
  while(t>u[l]) l++;
  l--;
  if(l<Degree) l=Degree;
  for(int j=0;j<Degree;j++)
  {
   for(int i=l-Degree+1+j;i<=l;i++)
   {
    double alfa = (t - u[i])/(u[i+Degree-j]-u[i]);
    points[i]=(1-alfa)*points[i-1]+alfa*points[i];
   }
  }
  return points[l];
 }