Laskennallinen geometria
Siirry navigaatioon
Siirry hakuun
![](http://chped.net/https/upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Point_quadtree.svg/160px-Point_quadtree.svg.png)
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.
![](http://chped.net/https/upload.wikimedia.org/wikipedia/commons/thumb/2/2d/Point_in_polygon_problem.svg/158px-Point_in_polygon_problem.svg.png)
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.