Laskennallinen geometria
Siirry navigaatioon
Siirry hakuun
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
[muokkaa | muokkaa wikitekstiä]- 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.