Zobrazení zdroje stránky Geometrie/Výpočet průsečíku křivek

== Průsečík dvou křivek ==

[[Soubor:Prusecik krivek 16 2.png]]

=== Algoritmus ===
Pro nalezení průsečíku (nebo více průsečíků) dvou křivek v rovině je
použit následující jednoduchý algoritmus (implementovaný v souboru Intersection.cs,
metoda <code>public void Find_Intersection()</code>):
Mějme křivku C1 a křivku C2. Každou křivku si rozdělíme na jednotlivé
body - čím jich bude více, tím to bude přesnější. Počet bodů je uložen
v proměnné <code>int pocet</code>.

<syntaxhighlight lang="csharp">
par_c1_f = (double)((RichPoint)curve1.ControlPoly[0]).T;// první bod křivky C1
par_c1_l = (double)((RichPoint)curve1.ControlPoly[curve1.ControlPoly.Count-1]).T;//poslední bod křivky C1

par_c2_f = (double)((RichPoint)curve2.ControlPoly[0]).T;// první bod křivky C2
par_c2_l = (double)((RichPoint)curve2.ControlPoly[curve2.ControlPoly.Count-1]).T;//poslední bod křivky C2

// vzdál. mezi prvním a posledním bodem křivky C1 (resp. C2)
// rozdělený na požadovaný počet bodů
krok_1 = (par_c1_l - par_c1_f) / pocet;
krok_2 = (par_c2_l - par_c2_f) / pocet;
</syntaxhighlight>

Jádrem algoritmu jsou dva vnořené cykly: v prvním beru postupně bod po bodu z křivky C1 a
pro každý tento bod změřím vzdálenost mezi ním a každým bodem z křivky C2 v druhém cyklu.
Pokud je vzdálenost bodů menší než hodnota proměnné <code>double presnost</code> (ta udává povolenou odchylku),
potom jsem našel průsečík obou křivek. Vzdálenost bodů počítám podle vzorce:

<math>|AB|=\sqrt{(A_{x}-B_{x})^2+(A_{y}-B_{y})^2}</math>

Tomu v programu odpovídá řádek:<br />
<code>System.Math.Sqrt(System.Math.Abs(((p1.X-p2.X)*(p1.X-p2.X))+((p1.Y-p2.Y)*(p1.Y-p2.Y))))</code><br />
kde:
<pre>
     p1.X - x-ová souřadnice bodu A
     p1.Y - y-ová souřednice bodu A
     p2.X - x-ová souřadnice bodu B
     p2.Y - y-ová souřadnice bodu B
</pre>

=== Find_Intersection() ===
Zde je kód hlavní metody.

<syntaxhighlight lang="csharp">
public void Find_Intersection()
{
	double par_c1_f,par_c1_l,par_c2_f,par_c2_l;
	double f,g,krok_1,krok_2;

	RichPoint drp;

	par_c1_f = (double)((RichPoint)curve1.ControlPoly[0]).T;
	par_c1_l = (double)((RichPoint)curve1.ControlPoly[curve1.ControlPoly.Count-1]).T;

	par_c2_f = (double)((RichPoint)curve2.ControlPoly[0]).T;
	par_c2_l = (double)((RichPoint)curve2.ControlPoly[curve2.ControlPoly.Count-1]).T;

	krok_1 = (par_c1_l - par_c1_f) / pocet;
	krok_2 = (par_c2_l - par_c2_f) / pocet;

	for (int i=0;i<pocet;i++)
	{
		Vector p1;
		f = (i * krok_1) + par_c1_f;
		p1 = curve1.GetPoint(f);
		for (int j=0;j<pocet;j++)
		{
			Vector p2;
			g = (j * krok_2) + par_c2_f;
			p2 = curve2.GetPoint(g);
			if (System.Math.Sqrt(System.Math.Abs(((p1.X-p2.X)*(p1.X-p2.X))+((p1.Y-p2.Y)*(p1.Y-p2.Y)))) < presnost)
			{
				drp = new RichPoint(p2,0);
				drp.Selected = true;
				control.RichPoints.Add(drp);
				j+=3;
				i+=3;
			}
		}
	}
}
</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|Výpočet průsečíku křivek]]