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:

Zobacz też

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.