Přehled studia |
Přehled oborů |
Všechny skupiny předmětů |
Všechny předměty |
Seznam rolí |
Vysvětlivky
Návod
Webová stránka:
https://cw.fel.cvut.cz/wiki/courses/B4M39DPG
Anotace:
Předmět má studující seznámit s datovými strukturami používanými v algoritmech použivaných v počítačové grafice, zejména pro vyhledávání. Důraz je kladen na základní a hierarchické datové struktury nad bodovými a objektovými daty ve 2D a 3D pro reprezentaci prostorových dat, vyhledávání nejbližšího souseda, sledování paprsku. Na cvičení studující řeší každý sám individuální projekt realizací algoritmu v C++ a získá vhled a zkušenost do konkrétního problému.
Cíle studia:
Cílem studia je se seznámit s datovými strukturami používanými v počítačové grafice pro 2D a 3D data, typicky pro problém vyhledávání, získat jak teoretické tak praktické zkušenosti s realizací netriviálního algoritmu typicky realizující hierarchickou datovou strukturu a s realizací projektu zahrnující studium algoritmu, jeho implementaci, realizaci, odladění, testování, prezentaci a dokumentaci.
Obsah:
Studenti získají body na základě semestrálního projektu skládající se z teoretické prezentace algoritmu, implementace algoritmu včetně jeho testování a odladění, dokumentace zdrojových kódů algoritmu, sepsání technického reportu a závěrečné prezentace o svém projektu. Písemný test v rámci zkoušky je dán obsahem přednášek.
Osnovy přednášek:
| 1. | | Přehled přednášek, zopakování řazení a vyhledávání nad čísly, základní přehled algoritmů probíraných v předmětu, pravidla hry. Úvod do hierarchických a pravidelných datových struktur. |
| 2. | | Jednoduché geometrické entity a jejich reprezentace |
| 3. | | Pokročilé geometrické entity a jejich reprezentace |
| 4. | | Incidenční operace mezi entitami používané v počítačové grafice, cenový model. |
| 5. | | Hierarchické a regulární datové struktury, cenový model |
| 6. | | Datové struktury a reprezentace bodových dat. |
| 7. | | Objektové a obrazkové reprezentace ve 2D a 3D. |
| 8. | | Algoritmy pro vyhledávání nejbližších sousedů. |
| 9. | | Aproximativní algoritmy pro vyhledávání nejbližších sousedů, aplikace v počítačové grafice |
| 10. | | Datové struktury pro algoritmy sledování a vrhání paprsku a jejich aplikace I. |
| 11. | | Datové struktury pro algoritmy sledování a vrhání paprsku a jejich aplikace II. |
| 12. | | Datové struktury a algoritmy pro výpočet viditelnosti III. |
| 13. | | Algoritmy pro vyhledávání ve vysoko-dimenzionálních prostorech. |
| 14. | | Rezerva. |
Osnovy cvičení:
| 1. | | Úvod ke cvičení, vstupní test. |
| 2. | | Popis semestrálních úloh v kostce. |
| 3. | | Výběr domácích úloh studenty, konzultace k domácím úlohám. |
| 4. | | Seznámení se s programovým prostředím v C++. |
| 5. | | Příklady na incidenční operace. |
| 6. | | Příklady na incidenční operace. |
| 7. | | Výkladová prezentace domácích úloh (10 studenti) |
| 8. | | Výkladová prezentace domácích úloh (10 studenti) |
| 9. | | Výkladová prezentace domácích úloh, rezerva, konzultace k semestrálním projektům. |
| 10. | | Písemný test na 60 minut. |
| 11. | | Konzultace k semestrálním projektům. |
| 12. | | Demonstrační prezentace domácích úloh. (10 studentů) |
| 13. | | Demonstrační prezentace domácích úloh. (10 studentů) |
| 14. | | Rezerva |
Literatura:
| 1. | | Samet, H: The Design and Analysis of Spatial Data Structures, Addison Wesley 1994. |
| 2. | | Samet, H: Applications of Spatial Data Structures, Addison Wesley, 1990. |
| 3. | | Laurini, R. and Thompson D.: Fundamentals of Spatial Information Systems, Academic Press 1992. |
| 4. | | Samet, H: Foundations of Multidimensional and Metric Data Structures, Morgan Kaufmann Publishers, 2006. |
| 5. | | E. Langetepe and G. Zachmann: Geometric Data Structures for Computer Graphics, 2006. |
| 6. | | C. Ericson: Real Time Collision Detection, Morgan Kauffman Publishers, 2005. |
| 7. | | G. van den Bergen: Collision Detection in Interactive 3D Environments, Elsevier, 2004. |
| 8. | | D. P. Mehta and S. Sahni: Handbook of Data Structures and Applications, Chapman and Hall/CRC, 2004 |
Požadavky:
Časová a paměťová složitost algoritmu, binární stromy a haldy, vyvažování stromů, vyhledávací algoritmy, prioritní fronty, základy architektury von Neumann a základní znalost jazyka C++. Znalost jazyka C++ bude krátce ověřena na prvním cvičení předmětu.
Poznámka:
Klíčová slova:
třídění, vyhledávání, multidimenzionální datové struktury, datové struktury pro metodu vrhaní paprsku, vyhledávání nejbližšího souseda, výpočty viditelnosti
Předmět je zahrnut do těchto studijních plánů:
| Stránka vytvořena 10.6.2026 12:51:45, semestry: L/2027-8, Z/2026-7, Z/2028-9, Z/2027-8, L/2025-6, L/2026-7, L/2029-30, L/2028-9, připomínky k informační náplni zasílejte správci studijních plánů |
Návrh a realizace: I. Halaška (K336), J. Novák (K336) |