Laskennallinen geometria

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

• 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.