Předmět AGU jsem měl v zimním semestru roku 2017/2018 a probíraným tématem byly algoritmy používané při práci s geometrií. Ať už v počítačových hrách, při analýze obrazu nebo jiných výpočtech. Na cvičení jsme měli za úkol některé z těchto algoritmů naprogramovat a vizualizovat. Výsledkem tedy byly animace, které jsme se rozhodl natočit programem OBS a následně nahrát na YouTube i s drobným komentářem a vysvětlením.
Videa a Github
Kromě videí na YouTube jsou také zdrojové kódy v C++ na Githubu. Pro možnost spuštění je ale nutné připojit knihovnu OpenCV.
Test bodu v polygonu (Point in polygon test)
Jedna z lehčích úloh spočívala v zjištění, zda bod leží či neleží uvnitř konvexního polygonu v logaritmickém čase. Spočívá v půlení intervalu všech bodů a kontroly, na které straně od hrany bod leží.
Nalzení konvexního obalu (Convex hull)
Konvexní obal je takový konvexní polygon, ve kterém leží všechny body. Pro nalezení je použit algoritmus Jarvis march, známý také algoritmus balení dárku.
Nejbližší dvojice bodů na přímce (Closest pair of points - 1D)
Všechny zmíněné problémy mají více možností řešení. Nalezení nejbližší dvojice bodů na přímce se dá řešit metodou Rozděl a panuj, podobně jako řešení ve 2D. Znázorněna je ale metoda seřazení bodů a následného lineárního průchodu, která je intuitivnější.
Nejbližší dvojice bodů v rovině (Closest pair of points - 2D)
Nejtěžší úkol, který jsem vizualizoval bylo určení nejbližší dvojice bodů v rovině pomocí metody rozděl a panuj. Řešení problémů je vysvětleno ve videu, případně detailněji na stránce geeksforgeeks.org.
Další algoritmy a jiné vizualizace
Další na řadě byly algoritmy jako Triangulace bodů v rovině, určení Voroného diagramu, ke kterému je také pěkná vizualizace, intervalové vyhledávání, využití grafu viditelnosti a mnoho dalšího.
Předmět už mám za sebou, tak můžu dělat chytrého. Jednoduché to ale nebylo, za vším je jen spousta matematiky, která šla vždy jedním uchem tam a druhým ven. Naštěstí zkoušející byl p. Sojka, a kdo ho zná ví, že tu matiku po nikom nechce.
K tomuto článku již není možné přidávat další komentáře
Komentáře
nice article