Algoritmy pro Minkowského součet mnohoúhelníků
Algorithms for Minkowski sums of polygons
bachelor thesis (DEFENDED)
![Document thumbnail](/bitstream/handle/20.500.11956/185042/thumbnail.png?sequence=7&isAllowed=y)
View/ Open
Permanent link
http://hdl.handle.net/20.500.11956/185042Identifiers
Study Information System: 230551
Collections
- Kvalifikační práce [10925]
Author
Advisor
Referee
Příhoda, Pavel
Faculty / Institute
Faculty of Mathematics and Physics
Discipline
Mathematics for Information Technologies
Department
Department of Algebra
Date of defense
12. 9. 2023
Publisher
Univerzita Karlova, Matematicko-fyzikální fakultaLanguage
Czech
Grade
Excellent
Keywords (Czech)
Minkowského součet|Winding number|Nekonvexní mnohoúhelníky|Konvoluční metoda|Rozkladová metodaKeywords (English)
Minkowski sum|Winding number|Non-convex polygons|Convolution Method|Decomposition MethodTato bakalářská práce se zabývá Minkowského součtem dvou nekonvexních mnoho- úhelníků v rovině, konkrétně pak popisem a porovnáním dvou metod pro výpočet Min- kowského součtu: rozkladové metody a konvoluční metody. V této práci jsou obě tyto metody blíže představeny, včetně potřebných definic a ilustrativních obrázků. V závě- rečné kapitole jsou pak obě metody porovnány za pomoci C++ knihovny CGAL na různých vstupech. 1
This bachelor's thesis deals with the Minkowski sum of two non-convex polygons in the plane. Specifically, it focuses on describing and comparing two methods for computing the Minkowski sum: the decomposition method and the convolution method. This thesis provides a detailed presentation of both methods, including necessary definitions and illustrative images. In the final chapter, both methods are compared using the CGAL C++ library on various inputs. 1