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

Z Wikiknih

Obsah 1 Průsečík dvou křivek 1.1 Algoritmus 1.2 Find_Intersection() 2 Autoři

[editovat] Průsečík dvou křivek

[editovat] 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:

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

[editovat] 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;

	}
      }
  }
}

[editovat] 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.