Monotone polygons algorithms

Niniejsza praca poświęcona jest implementacji i analizie wybranych algorytmów wielokątów monotonicznych. Wielokąt monotoniczny to wielokąt, który dla pewnej prostej L jest przecinany przez każdą prostą prostopadłą do L w co najwyżej dwóch punktach. Wielokąt wypukły jest monotoniczny względem dowolnej prostej L.W pracy omówione zostały trzy algorytmy triangulacji: algorytm triangulacji wachlarzowej działający w czasie liniowym dla dowolnego wielokąta wypukłego, algorytm triangulacji wielokąta y-monotonicznego oraz algorytm triangulacji z minimalizacją długości cięciw wykorzystujący programowanie dynamiczne. Opisany został także algorytm podziału monotonicznego wielokąta prostego wykorzystujący technikę zamiatania płaszczyzny i działający w czasie liniowo-logarytmicznym. Każdy z powyższych algorytmów zaimplementowany został w wersji wykorzystującej graf jako strukturę danych wyjściowych, oraz w wersji wykorzystującej w tym celu mapę planarną. W algorytmach wykorzystujących graf złożoność obliczeniowa zgadza się z teoretyczną, a w przypadku wersji wykorzystujących mapę planarną złożoność trochę pogarsza się, co jest ceną za posiadanie informacji o strukturze topologicznej podziału. Dodatkowo algorytm triangulacji z minimalizacją długości cięciw opracowany został w dwóch wersjach: iteracyjnej i rekurencyjnej. Zaimplementowano również algorytm wyznaczania kierunków monotoniczności wielokąta działający w czasie liniowym.Poprawność wyników wszystkich algorytmów została przetestowana, a ich złożoność obliczeniowa sprawdzona eksperymentalnie i opisana.

This paper is devoted to analysis and implementation of selected algorithms for monotone polygons. A monotone polygon is a polygon that, for a line L, is intersected by any line perpendicular to L in at most two points. A convex polygon is monotone with respect to any straight line L.In this paper three triangulation algorithms are presented: a fan triangulation algorithm that works in linear time for any convex polygon, an y-monotone polygon triangulation algorithm and a triangulation algorithm which minimizes chords lengths and uses dynamic programming. A monotone polygon partitioning algorithm, which uses sweep line technique and runs in linearithmic time is also presented. Each of the above algorithms has been implemented in a version which uses a graph as an output data structure, as well as in a version using planar map for this purpose. In implementations using graphs, algorithm time complexity corresponds to theoretical, but in implementations using planar maps, time complexity is a bit worse, which is a cost for having direct access to the topological structure of a partition. Additionally, the triangulation algorithm which minimizes chords lengths was developed in two versions: iterative and recursive. An algorithm for finding monotone directions of a given polygon, which runs in linear time, is also presented.Correctness of all algorithms was tested as well as their real computational complexity.