Geometric algorithms with Python

Geometria obliczeniowa zajmuje się badaniem algorytmów i struktur danych rozwiązujących problemy zdefiniowane z użyciem obiektów geometrycznych (punkty, odcinki, proste, wielokąty). W pracy przedstawiono implementację w języku Python wybranych algorytmów geometrii obliczeniowej na płaszczyźnie. Zbudowano szereg klas reprezentujących obiekty geometryczne, a także zebrano narzędzia często używane w algorytmach geometrycznych.Przykładowe operacje to znajdowanie zorientowanego pola równoległoboku, sprawdzanie przecinania się odcinków, sortowanie punktów względem kąta.Przygotowano trzy algorytmy wyznaczające otoczkę wypukłą dla skończonego zbioru punktów: algorytm Grahama, algorytm Jarvisa i algorytm quickhull.Zaimplementowano dwa algorytmy sprawdzające zawieranie się punktu w wielokącie: metoda liczby przecięć i metoda liczby nawinięć. Metoda rotujących suwmiarek została wykorzystana do wygenerowania wszystkich par punktów antypodycznych, które z kolei pozwalają szybko wyznaczyć parę najdalszych punktów. Zaimplementowano algorytm wyznaczający orientację wielokąta prostego. Są algorytmy testujące, czy wielokąt jest prosty (metoda siłowa) i czy wielokąt prosty jest wypukły.

Computational geometry is devoted to study algorithms and data structures solving problems involving geometric objects (points, segments, lines, polygons). Python implementation of selected computational geometry algorithmsin the plane is presented. Separate clases representing geometric object were built and tools used in geometric algorithms were collected. Exemplary operations: finding the oriented area of a parallelogram, testing segments intersections, sorting points by angles.Three algorithms for computing the convex hull for a finite set of points are presented: the Graham scan algorithm,the gift wrapping (Jarvis march) algorithm, and the quickhull algorithm.Two algorithms solving the point in polygon problem are implemented: the crossing number method and the winding number method. The method of rotating calipers is used to generate all antipodal pairs of points for a convex polygon.Antipodal pairs are used to find a pair of furthest points. The algorithm for finding the orientation of a simple polygonis also implemented. There are algorithms for testing if a polygon is simple (brute force)and if a simple polygon is convex.