Geometrie/Výpočet průsečíku křivek

Průsečík dvou křivek

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 public void Find_Intersection()): 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é int pocet.

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;

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é double presnost (ta udává povolenou odchylku), potom jsem našel průsečík obou křivek. Vzdálenost bodů počítám podle vzorce:

$|AB|={\sqrt {(A_{x}-B_{x})^{2}+(A_{y}-B_{y})^{2}}}$

Tomu v programu odpovídá řádek:
System.Math.Sqrt(System.Math.Abs(((p1.X-p2.X)*(p1.X-p2.X))+((p1.Y-p2.Y)*(p1.Y-p2.Y))))
kde:

     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

Find_Intersection()

Zde je kód hlavní metody.

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;
			}
		}
	}
}

Autoři

Tento text vypracovali studenti Univerzity Palackého v Olomouci katedry Matematické informatiky jako zápočtový úkol do předmětu Počítačová geometrie.