BrziOmotač

Из Википедије, слободне енциклопедије

BrziOmotač je metod nalaženja konveksnog omotača konačnog skupa tačaka u ravni. Koristi podeli pa vladaj pristup sličan onom koji se koji se koristi u Kviksort algoritam, odakle i dobija svoje ime. Prosečna složenost ovog algoritma je O(n * log(n)), a u najgorem slučaju je O(n2) (kvadratna).

Algoritam[уреди]

Koraci 1-2: Podela tačaka na dva skupa

Pod prosečnim okolnostima algoritam funkcioniše prilično dobro, ali obrada se usporava u slučajevima visoke simetrije i ukoliko tačke leže na kružnici. Algoritam može da se rastavi na sledeće korake:

  1. Naći tačke sa minimalnom i maksimalnom x koordinatom, one moraju biti deo konveksnog omotača;
  2. Formirati liniju od te dve tacke i iskoristiti je da bi se podelile u dva podskupa tacaka koje ce se obraditi rekurzivno;
  3. Odrediti tačku sa jedne strane linije sa maksimalnom razdaljinom od linije. Dve prethodno odabrane linije i ova nova sada formiraju trougao;
  4. Tačke koje se nalaze u trouglu ne mogu biti deo konveksnog omotača te se ignorišu u sledećim koracima;
  5. Ponoviti prethodna dva koraka nad dve linije koje formiraju trougao (ne osnovnom linijom);
  6. Nastaviti sa time dok ne preostane vise tačaka, rekurzija stigne do kraja i tačke koje smo odabirali ne formiraju konveksni omotač;
Koraci 3-5: Nalaženje tačke sa najvećom razdaljinom i ignorisanje tačaka koje se nalaze u trouglu i ponavljanje koraka
Korak 6: Rekurzivno nastaviti algoritam dok nema više preostalih tačaka

Reference[уреди]