IB111
Programování a algoritmizace
Grafika
Světlo, barvy
Zdroj: Wikipedia Commons
Aditivní barevný model
Zdroj:
Wikipedia Commons
Substraktivní barevný model
Zdroj:
Wikipedia Commons
Bitmapa – rastrová grafika
 BMP, JPG, GIF
Ztrátová komprese
 JPG
Vektorová grafika
 CDR,
AI,
EPS…
Zdroj:
justskins.com
Vektorová a bitmapová grafika
Zdroj:
Wikipedia Commons
Příklady algoritmů
 Algoritmy používané v grafice
 Kreslení úseček a jiných křivek
 Ořezávání
 Vybarvování ploch
 Změny barev
 Řešení viditelnosti objektů
Úsečka
 Bresenhamův algoritmus
 Digitálně diferenciální algoritmus (DDA)
Zdroj:
Wikipedia Commons
Algoritmus DDA
Vyplňování souvislé oblasti
 Semínkové záplavové vyplňování
Algoritmus
 Naivní rekurse
 Hledání následníků
Semínkové záplavové vyplňování
Zdroj:
Wikipedia Commons
Souvislost oblasti
 Souvislost oblasti
 4souvislá
oblast
 8souvislá
oblast
http://nb.vse.cz/~simunek/it418/2d/vypln2D/Vypln2D.Demo1.html
Konvexní obal
 Vstup: množina bodů v rovině
 Souřadnice xi,yi
 Výstup: uspořádaný seznam bodů
tvořících konvexní obal
Graham scan
 Najdu bod s nejnižší y souřadnicí
 Označím ho P
 Pro všechny body vytvářím
„spojnici“ s P
 Spočítám úhel (s x-ovou osou)
 Seřadím body podle tohoto úhlu
 Procházím sekvenci k dalším bodům
 Pokud „zahýbám vlevo“
 OK, potračuju dál
 Pokud „zahýbám vpravo“
 Vypustím předposlední bod z konvexního obalu
Zdroj:
Wikipedia Commons
Graham scan (1)
Graham scan (2)
Voroného diagram
 Vstup: množina bodů
 Výstup: rozdělení roviny na oblasti „ke
kterému bodu je odsud nejblíže“
 Aplikace:
 Vyhledávání
 Umísťování nových bodů (např. restaurace)
 Plánování cest (např. roboti)
Voroného diagram
Zdroj:
Wikipedia Commons