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.