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(n²) (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

• Barber, C. Bradford; Dobkin, David P.; Huhdanpaa, Hannu (1. 12. 1996). „The quickhull algorithm for convex hulls” (PDF). ACM Transactions on Mathematical Software. 22 (4): 469—483. doi:10.1145/235815.235821.