Geometria obliczeniowa

Geometria obliczeniowa – dział algorytmiki, który wyodrębnił się w latach 70. XX wieku, zajmujący się algorytmami i strukturami danych pozwalającymi efektywnie wykonywać działania na obiektach geometrycznych, takich jak zbiory punktów, odcinków, wielokątów, okręgów. Wyniki geometrii obliczeniowej mają istotne znaczenie w wielu dziedzinach informatyki i inżynierii, takich jak grafika komputerowa, robotyka, symulacje komputerowe, bazy danych, projektowanie wspomagane komputerowo. Przykładowe problemy rozważane w tej dziedzinie: * wyznaczanie pary najbliższych lub najdalszych punktów; * wyznaczanie wszystkich przecięć zbioru odcinków, okręgów itp. (wykrywanie kolizji); * wyznaczanie otoczki wypukłej; * triangulacja wielokątów; * przecięcia wielokątów, wieloboków, prostokątów, prostych (w tym stwierdzenie faktu przecięcia, wyznaczenie punktów przecięć, realizacja operacji boolowskich); * wyszukiwanie geometryczne – które obiekty, np. punkty, odcinki, leżą wewnątrz prostokąta, okręgu itp.; * okienkowanie; * planowanie ruchu robota; * odtwarzanie powierzchni z chmury punktów. Przykładowe algorytmy i struktury danych: * triangulacja Delone, * algorytm Cohena-Sutherlanda, * algorytm Sutherlanda-Hodgmana, * algorytm Jarvisa, * Quickhull, * drzewo kd, * drzewo przedziałowe, * drzewo czwórkowe.