Nakładanie map w geometrii obliczeniowej

licenciate
dc.abstract.enA computational geometry algorithm for map overlay has been developed and implemented in the thesis using Python. The algorithm represents steps, which are needed for overlaying two maps. A map is a plane connected graph. Doubly connected edge lists have been added to the representation of abstract graphs. This way it is possible to walk along the border of any face if one of its edges is given.The algorithm checks all possible cases of the intersection of two edges and transforms a copy of the first input map into a maps overlaying result.In addition, during the implementation of the map overlay algorithm, a new method has been added. This method generates edges sequentially and maintains map connectivity in each iteration. This algorithm is based on breadth-first search algorithm. Another newly added methods are adding a leaf and adding a chord to the map.The following geometrical structures were used for implementation: point, segment, rectangle, graph.pl
dc.abstract.plW pracy został opracowany i zaimplementowany w języku Python, algorytm z geometrii obliczeniowej, polegający na nakładaniu map. Algorytm przedstawia spis kroków, wymaganych do połączenia dwóch wejściowych map. Mapa jest to graf spójny płaski. Do reprezentacji abstrakcyjnego grafu została dodana struktura podwójnie powiązanych list krawędzi. W ten sposób jest możliwe obieganie każdej ściany mapy po podaniu dowolnej krawędzi do niej należącej.Algorytm zawiera sprawdzanie wszystkich możliwości przecinania się dwóch krawędzi oraz przekształcenie kopii pierwszej wejściowej mapy w mapę, reprezentującą wynik nakładania.Dodatkowo, przy opracowaniu algorytmu nakładania map, powstała metoda generująca krawędzie w taki sposób, aby mapa po dodaniu każdej kolejnej krawędzi miała postać spójną. Ten algorytm jest oparty na algorytmie przeszukiwania grafu wszerz. Kolejne nowo dodane metody to dodawanie liścia i cięciwy do mapy.W implementacji wykorzystano następujące struktury geometryczne: punkt, odcinek, prostokąt, graf.pl
dc.affiliationWydział Fizyki, Astronomii i Informatyki Stosowanejpl
dc.areaobszar nauk ścisłychpl
dc.contributor.advisorKapanowski, Andrzej - 100452 pl
dc.contributor.authorSarnavska, Annapl
dc.contributor.departmentbycodeUJK/WFAISpl
dc.contributor.reviewerKorcyl, Grzegorzpl
dc.contributor.reviewerKapanowski, Andrzej - 100452 pl
dc.date.accessioned2020-10-21T19:18:41Z
dc.date.available2020-10-21T19:18:41Z
dc.date.submitted2020-09-15pl
dc.fieldofstudyinformatykapl
dc.identifier.apddiploma-145105-243261pl
dc.identifier.projectAPD / Opl
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/250236
dc.languagepolpl
dc.subject.enplane graph, map overlay, computational geometry, connected graph, doubly connected edge listpl
dc.subject.plgraf płaski, nakładanie map, geometria obliczeniowa, graf spójny, podwójnie wiązana lista krawędzipl
dc.titleNakładanie map w geometrii obliczeniowejpl
dc.title.alternativeMap overlay in computational geometrypl
dc.typelicenciatepl
dspace.entity.typePublication
dc.abstract.enpl
A computational geometry algorithm for map overlay has been developed and implemented in the thesis using Python. The algorithm represents steps, which are needed for overlaying two maps. A map is a plane connected graph. Doubly connected edge lists have been added to the representation of abstract graphs. This way it is possible to walk along the border of any face if one of its edges is given.The algorithm checks all possible cases of the intersection of two edges and transforms a copy of the first input map into a maps overlaying result.In addition, during the implementation of the map overlay algorithm, a new method has been added. This method generates edges sequentially and maintains map connectivity in each iteration. This algorithm is based on breadth-first search algorithm. Another newly added methods are adding a leaf and adding a chord to the map.The following geometrical structures were used for implementation: point, segment, rectangle, graph.
dc.abstract.plpl
W pracy został opracowany i zaimplementowany w języku Python, algorytm z geometrii obliczeniowej, polegający na nakładaniu map. Algorytm przedstawia spis kroków, wymaganych do połączenia dwóch wejściowych map. Mapa jest to graf spójny płaski. Do reprezentacji abstrakcyjnego grafu została dodana struktura podwójnie powiązanych list krawędzi. W ten sposób jest możliwe obieganie każdej ściany mapy po podaniu dowolnej krawędzi do niej należącej.Algorytm zawiera sprawdzanie wszystkich możliwości przecinania się dwóch krawędzi oraz przekształcenie kopii pierwszej wejściowej mapy w mapę, reprezentującą wynik nakładania.Dodatkowo, przy opracowaniu algorytmu nakładania map, powstała metoda generująca krawędzie w taki sposób, aby mapa po dodaniu każdej kolejnej krawędzi miała postać spójną. Ten algorytm jest oparty na algorytmie przeszukiwania grafu wszerz. Kolejne nowo dodane metody to dodawanie liścia i cięciwy do mapy.W implementacji wykorzystano następujące struktury geometryczne: punkt, odcinek, prostokąt, graf.
dc.affiliationpl
Wydział Fizyki, Astronomii i Informatyki Stosowanej
dc.areapl
obszar nauk ścisłych
dc.contributor.advisorpl
Kapanowski, Andrzej - 100452
dc.contributor.authorpl
Sarnavska, Anna
dc.contributor.departmentbycodepl
UJK/WFAIS
dc.contributor.reviewerpl
Korcyl, Grzegorz
dc.contributor.reviewerpl
Kapanowski, Andrzej - 100452
dc.date.accessioned
2020-10-21T19:18:41Z
dc.date.available
2020-10-21T19:18:41Z
dc.date.submittedpl
2020-09-15
dc.fieldofstudypl
informatyka
dc.identifier.apdpl
diploma-145105-243261
dc.identifier.projectpl
APD / O
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/250236
dc.languagepl
pol
dc.subject.enpl
plane graph, map overlay, computational geometry, connected graph, doubly connected edge list
dc.subject.plpl
graf płaski, nakładanie map, geometria obliczeniowa, graf spójny, podwójnie wiązana lista krawędzi
dc.titlepl
Nakładanie map w geometrii obliczeniowej
dc.title.alternativepl
Map overlay in computational geometry
dc.typepl
licenciate
dspace.entity.type
Publication
Affiliations

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
9
Views per month
Views per city
Wroclaw
2
Dublin
1
Krakow
1

No access

No Thumbnail Available