Laskennallinen geometria

Wikipediasta
Siirry navigaatioon Siirry hakuun
Qaudtree on yksi indeksointimenetelmä pistemuotoiselle datalle.

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.

Point in Polygon -ongelma. Millainen algoritmi tarvitaan selvittämään, onko piste monikulmion sisällä.

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.