Map overlay in computational geometry

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.

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.