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.
Linki zewnętrzne
- Eric W.E.W. Weisstein Eric W.E.W., Computational Geometry, [w:] MathWorld, Wolfram Research (ang.). [dostęp 2023-06-01].
- Computational geometry (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org, [dostęp 2023-06-18].
- p
- d
- e
Działy geometrii
geometrie |
| ||||||||
---|---|---|---|---|---|---|---|---|---|
powiązane dyscypliny |
|
- p
- d
- e
Działy matematyki
działy ogólne |
| ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
działy czyste |
| ||||||||||||||||||
działy stosowane |
| ||||||||||||||||||
powiązane zajęcia |
|
- p
- d
- e
Informatyka teoretyczna
główne obszary |
|
---|---|
wybrane zagadnienia |
|