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.

Zobacz też

• metody numeryczne
• badania operacyjne
• optymalizacja

Bibliografia

• Mark de Berg: Geometria obliczeniowa : algorytmy i zastosowania. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007. ISBN 978-83-204-3244-2. 
• Franco P. Preparata, Michael Ian Shamos: Geometria obliczeniowa : wprowadzenie. Gliwice: Helion, 2003. ISBN 83-7361-098-7.