Triangulacja Delaunaya w geometrii obliczeniowej

Python implementation of five algorithms finding a Delaunaytriangulation in computational geometry is presented.A Delaunay triangulation of a given set P of points in the planeis a triangulation such that no point in P is inside the circumcircle of any triangle from the triangulation.Delaunay triangulations are used for modelling terrain, automatic mesh generation, and other applications.The following triangulation algorithms are prepared:a naive algorithm,the Lawson flipping algorithm,the incremental Bowyer-Watson algorithm,a divide and conquer algorithm by Lee and Schachter,and the quickhull algorithm.The algorithms were tested and they can be run for a givenpoint set by means of a command line program or a programwith graphical user interface.Triangulation algorithms are described in detail together withauxiliary data structures.

W pracy przedstawiono implementację w języku Python pięciu algorytmówwyznaczających triangulację Delaunaya w geometrii obliczeniowej.Triangulacja Delaunaya jest to taka triangulacja zbioru punktów Pna płaszczyźnie, że żaden punkt ze zbioru P nie znajduje sięwewnątrz okręgu opisanego na trójkącie należącym do triangulacji.Triangulacja Delaunaya jest używana m.in. do modelowania terenu,automatycznego generowania meshu.Przygotowane algorytmy triangulacji to algorytm naiwny,metoda odwróceń Lawsona,algorytm inkrementacyjny Bowyera-Watsona,algorytm rekurencyjny Lee-Schachtera oparty na metodzie dziel i zwyciężaj,oraz algorytm quickhull.Algorytmy zostały przetestowane i mogą być uruchamiane dla podanegozbioru punktów przy pomocy programu wiersza poleceńlub programu z interfejsem graficznym.Algorytmy triangulacji zostały szczegółowo opisane (pseudokody),łącznie z pomocniczymi strukturami danych.