Zobrazení zdroje stránky Geometrie/Racionální algoritmus de Casteljau

== Popis ==

Jestliže položíme

<math> P_i^0 = P_i </math> a <math> w_i^0 = w_i </math>, pak pro každé
<math> i = 0,...,n </math> platí:

<math> P_i^k = (1-u) \frac{w^{k-1}_{i-1}}{w_i^k}P_{i-1}^{k-1} +
u \frac{w_i^{k-1}}{w_i^k}P_i^{k-1} </math>,kde

<math>w_i^k = (1-u)w^{k-1}_{i-1} + uw_i^{k-1} </math>

Jak je vidět, jediným rozdílem oproti klasickému [[../Algoritmus de Casteljau|algoritmu de Casteljau]] je fakt, že do výpočtu zahrnujeme váhové parametry, a pro každý nový bod
spočítáme jeho poměrnou váhu vzhledem k bodům předešlým.

Pomocí váhových koeficientů lze měnit tvar Bézierovy křivky, s rostoucím
váhovým koeficientem se křivka k danému bodu "přibližuje".

== Algoritmizace ==
Syntetické algoritmy nad racionálními bézierovými křivkami jsou téměř
totožné jako algoritmy nad obyčejnými bézierovými křivkami, pouze se
počítá v o jednu dimenzi vyšším prostoru. V naší implementaci není
takový vektor zahrnut, proto se v následujících metodách počítá
s váhovou složkou zvlášť.

Nejprve si popišme pomocné metody a třídy:

; Vector : třída pro vektor ve 2D,
; RacionalRichPoint : třída pro racionální bod a jeho parametrizaci,
; Vector.lerp : metoda pro lineární interpolaci dvou bodů,
; ctrlPoly : řídící polygon.

=== public override Vector GetPoint ===
Funkce GetPoint slouží k výpočtu polohového vektoru příslušného k bodu
na křivce pro daný parametr.

<syntaxhighlight lang="csharp">
public override Vector GetPoint(double s)
{
	int n = ControlPoly.Count;
	double t = (s - StartParam)/(EndParam-StartParam);
	Vector[] points = new Vector[n];
	double[] weights = new double[n];
	for (int i=0;i<n;i++)
	{
		RacionalRichPoint rp = (RacionalRichPoint)ctrlPoly[i];
		weights[i] = rp.Weight;
		points[i] = rp.Locate*rp.Weight;
	}
	for (int j=0;j<n-1;j++)
		for (int i=0;i<n-1;i++)
		{
			points[i]=points[i].lerp(t,points[i+1]);
			weights[i] = weights[i]*(1-t)+weights[i+1]*t;
		}
	return points[0]*(1/weights[0]);
}
</syntaxhighlight>

=== public override void Split ===
Rozdělí Bézierovu křivku na dvě v bodě určeném parametrem s.
Používá modifikovaný algoritmus de Casteljau pro výpočet
bodu na křivce.

<syntaxhighlight lang="csharp">
public override void Split(double s, out Curve c1, out Curve c2)
{
	int n = ControlPoly.Count;
	if (n>=2)
	{
		double t = (s- StartParam)/(EndParam-StartParam);
		Vector[] points= new Vector[n];
		double[] weights= new double[n];
		Vector[] pointsc1 = new Vector[n];
		Vector[] pointsc2 = new Vector[n];
		double[] weightsc1 = new double[n];
		double[] weightsc2 = new double[n];
		for (int i=0;i<n;i++)
		{
			RacionalRichPoint rp = (RacionalRichPoint)ctrlPoly[i];
			weights[i] = rp.Weight;
			points[i] = rp.Locate*rp.Weight;
		}
		for (int j=0;j<n-1;j++)
		{
			pointsc1[j]= points[0]*(1/weights[0]);
			weightsc1[j]= weights[0];

			pointsc2[n-1-j]= points[n-1-j]*(1/weights[n-1-j]);
			weightsc2[n-1-j]= weights[n-1-j];
			for (int i=0;i<n-1;i++)
			{
				points[i]=points[i].lerp(t,points[i+1]);
				weights[i] = weights[i]*(1-t)+weights[i+1]*t;
			}
		}
		pointsc1[n-1]= points[0]*(1/weights[0]);
		weightsc1[n-1]= weights[0];
		weightsc2[0]= weights[0];
		pointsc2[0]= points[0]*(1/weights[0]);
		c1 = new RationalBezierSynteticly(pointsc1,weightsc1);
		c2 = new RationalBezierSynteticly(pointsc2,weightsc2);
	}
	else
	if (n==1)
	{
		c1 = new RationalBezierSynteticly(ctrlPoly);
		RacionalRichPoint rp = (RacionalRichPoint)ControlPoly[0];
		c2 = new RationalBezierSynteticly(new Vector[]{(Vector)rp.Locate.Clone()},new double[]{rp.Weight});
	}
	else
	{
		c1= new BezierSynteticly(new ArrayList());
		c2= new BezierSynteticly(new ArrayList());
	}
}
</syntaxhighlight>

=== public RationalBezierSynteticly IncreaseDegree ===
Funkce vrací křivku se zvýšeným stupněm.

<syntaxhighlight lang="csharp">
public void IncreaseDegree()
{
	for (int i=0;i<DegreeIncrement;i++)
	{
		IncreaseDegreeByOne();
	}
}

public void IncreaseDegreeByOne()
{
	double ti=0;
	int n = ControlPoly.Count;
	Vector[] points= new Vector[n];
	double[] weights= new double[n];
	// naklonovani
	RacionalRichPoint theLast = (RacionalRichPoint)ControlPoly[n-1];
	theLast = new RacionalRichPoint((Vector)theLast.Locate.Clone(),0,theLast.Weight);
	for (int i=0;i<n;i++)
	{
		RacionalRichPoint rp = (RacionalRichPoint)ctrlPoly[i];
		weights[i] = rp.Weight;
		points[i] = rp.Locate*rp.Weight;
	}

	for (int i=1;i<n;i++)
	{
		ti = ((double)i)/n;
		RacionalRichPoint rp = (RacionalRichPoint)this.ControlPoly[i];
		rp.Weight = weights[i]*(1-ti)+weights[i-1]*ti;
		rp.Locate = points[i].lerp(ti,points[i-1])*(1/rp.Weight);

	}
	this.ControlPoly.Add(theLast);
}
</syntaxhighlight>

== Autoři ==
Tento text vypracovali studenti [http://www.inf.upol.cz Univerzity Palackého v Olomouci] katedry Matematické informatiky jako zápočtový úkol do předmětu Počítačová geometrie.

[[Kategorie:Geometrie|Racionální algoritmus de Casteljau]]