Sweep line technique

W pracy przedstawiono implementację w języku Python wybranych algorytmów z geometrii obliczeniowej, które wykorzystują technikę zamiatania płaszczyzny. Wykorzystano reprezentacje podstawowych obiektów geometrycznych (punkt, odcinek, prostokąt), a także zaimplementowano struktury danych niezbędne do optymalnego działania algorytmów.Przygotowano trzy algorytmy do szukania przecięć w zbiorze odcinków: algorytm Bentleya-Ottmanna (korzysta ze zmodyfikowanego drzewa AVL) i algorytm Shamosa-Hoeya do odcinków w pozycji ogólnej oraz dodatkowy algorytm do odcinków pionowych i poziomych.Dodatkowo zaimplementowano trzy algorytmy do szukania pary najbliższych punktów na płaszczyźnie. Pierwszy algorytm wykorzystuje technikę zamiatania, dwa następne technikę dziel i zwyciężaj.Przedstawiono również implementację struktury danych drzewa czwórkowego, które może przechowywać punkty lub prostokątne obszary płaszczyzny. Drzewo czwórkowe pozwala na wykonanie szybkich operacji wyszukiwania danych na płaszczyźnie albo zwartego przechowywania informacji o prostokątnych fragmentach pewnego obszaru płaszczyzny.

Python implementation of selected computational geometry algorithms using a sweep line technique is presented. Standard geometrical objects are used (point, segment, rectangle) together with special data structures needed in optimal algorithms.Three algorithms for finding line segment intersections are prepared: the Bentley-Ottmann algorithm (using a modified AVL tree) and the Shamos-Hoey algorithm (general position is assumed), the special algorithm for horizontal and vertical line segments.Additionally, three algorithms for finding the closest pair of points in the plane are implemented. The first algorithm is using plane sweep, next algorithms are using the divide and conquer technique.A tree data structure called a quadtree is also presented. It is used to partition a rectangular region into four subregions (with additional data) or to maintain point sets with efficient lookup.