Algoritmizace geometrických úloh

Pavel O mně

Výjimečně napíšu o předmětu z mého studia na VŠB. A to proto, že výstupem je pár videí, vysvětlujících některé probírané algoritmy, které následně skončily na YouTube kanálu.

Algoritmizace geometrických úloh

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.

Přidat komentář

Právě odpovídáte na existující komentář. Zrušit

Komentáře

sumit

29.3.2018 08:16

nice article

Odpovědět

Novinky z blogu

Přidání balíčku do Composeru bez Packagist

Composer umožňuje přidat balíček, který není zveřejněn na Packagist. Stačí, aby byl ve veřejném či privátním git repozitáři, dostupný lokálně na serveru v jiné složce nebo...

Další články