Laskennallinen geometria

Laskennallinen geometria on tietojenkäsittelytieteen osa-alue joka tutkii algoritmeja liittyen geometrisiin ja spatiaalisiin ongelmiin. Laskennallisen geometrian algoritmeja käytetään esimerkiksi tietokoneavusteisessa suunittelussa (CAD-ohjelmistoissa), paikkatietojärjestelmissä, tietokonegrafiikassa ja robotiikassa.

Keskeisiä ongelmia ja tutkimuskohteita 

 Monikulmion pinta-alan laskenta.
 Kahden monikulmion leikkaus: Leikkaavatko kaksi (yksinkertaista) monikulmiota toisensa missään pisteessä?
 PIP-ongelma. Onko annettu piste p minkään monikulmion sisällä (tai rajalla).
 Lyhin reitti. Mikä on lyhin reitti pisteestä p pisteeseen o, siten että reitti ei risteä yhtään estettä (muita ei sallittuja geometrisia kohteita).
 Lähin naapuri. Annetun pisteen p lähimmän naapurin etsiminen.
 Spatiaaliset relaatiot: Etsi kaikki kohteet jotka toteuttavat annetun spatiaalisen relaation, esimerkiksi leikkauksen tai sisältyvyyden.
 Ikkunakysely (eng. Window query). Etsi kohteet jotka ovat annetun hakualueen (ikkunan) sisällä.
 Etäisyyskysely. Etsi kymmenen lähintä kohdetta kuviosta G, tai kohteet jotka ovat alle 20 yksikköä kohteesta G.
 Spatiaaliset indeksit (hakemistorakenteet). Esimerkiksi R-puu, Grid File, Quadtree jne.  

Laskennallinen tiede
Geometria