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.
Zobacz też metody numeryczne badania operacyjne optymalizacja
Bibliografia
Linki zewnętrzne [dostęp 2023-06-01]. Computational geometry , Encyclopedia of Mathematics, encyclopediaofmath.org, [dostęp 2023-06-18].
Kategoria:Algorytmika O