Računalniška geometrija
Računalniška geometrija v računalništvu se ukvarja z raziskovanjem algoritmov, ki rešujejo geometrijske probleme in delujejo nad geometrijskimi podatki.
Glavni razlog za razvijanje računalniške geometrije, je bil napredek v računalniški grafiki in računalniško podprtem načrtovanju. Druge pomembne vede, ki uporabljajo rešitve računalniške geometrije, so robotika(načrtovanje gibanja, izogibanje ovir, problemi vidnega polja), geografski informacijski sistemi (geodetske lokacije, kataster in načrtovanje poti), načrtovanje integriranih vezij, računalniško podprto inženirstvo (programiranje strojev NC in druge.
Osnovna raziskava računalniške geometrije je razvoj učinkovitih algoritmov in podatkovnih struktur za reševanje problemov izjav in izrekov nad geometrijskimi objekti, kot so točke, daljice, mnogokotniki, poliedri in drugi.
Za sodobne geografske sisteme, računalniško grafiko in integrirana vezja lahko problemi vsebujejo nekaj sto milijonov točk. Tukaj je razlika v času, časovne zahtevnosti O(N2) in O(N log N) v sekundah in dnevih računanja. Zato je v računalniški geometriji velik poudarek na časovni zahtevnosti algoritmov.
Pogosti problemi v računalniški geometriji so
[uredi | uredi kodo]- Booleove operacije nad mnogokotniki,
- problem najbližjega para točk
- konveksna ogrinjača,
- Delaunayeva triangulacija,
- presečišče dveh premic,
- triangulacija mnogokotnika,
- vsebnostni test,
- Voronojevi diagrami.
