pri vsetkych nasledujucich si predom zoradujeme data, aby sme s nimi mohli efektivnejsie manipulovat.
Grahamov algoritmus
- hladanie konvexnej obalky
1. zoradime body podla x
2. najdeme body zhora - horni retez a zdola - dolni retez
- pmin a pmax priradime obalke
- od pmin sa posuvame dalej po x osy a kazdy nasledujuci bod pridaem do obalky
- skontrolujeme uhol pi-1, pi, pi+1 (vektorovy sucin)
- ak konvexny - pridame dalsi bod
- ak konkavny - vypustime bod a vratime sa na pi-1
zlozitost je O(n*log(n))
Jarvisov algoritmus
- algoritmus balenia darcekov
1. vezmeme bod s minimalnou hodnotou y a vodorovnu priamku, ktora nim povedie
2. otocime priamkou okolo bodu, az narazime na novy bod
3. v novom bode povedieme priamku a znovu noou budeme otacat, az kym nenajdeme novy bod
- algoritmus je vhodny pre hladanie konvexnej obalky pre maly pocet bodov
- zlozitost O(kn), kde k je pocet bodov tvoriacich obalku a n je celkoby pocet bodov
Dalsim prikladom je zametacia technika, ktoru sme uz rozoberali, ta sa napriklad hodi na hladanie prisecnikov, alebo minimalnych bodov
Vonoreho diagram sa tiez da najst pomocou sweep line
- jedna sa o planarny graf, ktory nam umozni najst vzdy najblizsieho suseda
- kolko bodov tolko oblasti
- body v otvorenych oblastiach tvoria vrcholy obalky
- uzlom diagramu je stred kruznice opisanej v aspon troch bodoch
- najdenie vonoreho diagramu pomocou zametcej tehcniky je pekny priklad command and conquer pristupu k uloham geometrie
