Računalniška geometrija

Iz Wikipedije, proste enciklopedije

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.

Nekateri izmed teh problemov izgledajo tako preprosti, da jih pred štiridesetimi leti sploh niso obravnavali za probleme.

Problem najbližjega para točk. Imamo N točk v ravnini. Naša naloga je poiskati dvojico, ki sta najbližji. Za rešitev lahko izračunamo razdalje med vsemi pari točk, teh je N(N − 1)/2 , nato pa izberemo najkrajši par. Ta grob pristop ima časovno zahtevnost O(N²), kar pomeni, da je čas izvajanja sorazmeren s kvadratom števila vseh točk. Mejnik v računalniški geometriji je algoritem za rešitev problema najbližjih točk, ki ima časovno zahtevnost O(N log N).

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(N²) in O(N log N) v sekundah in dnevih računanja. Zato je v računalniški geometriji velik poudarek na časovni zahtevnosti algoritmov.