Nelipuutietorakenne ja sen toiminta käytännön sovelluksissa

Abstract

Erilaiset tietorakenteet ovat tietotekniikassa olennainen osa teknisiä toteutuksia ja niiden soveltuvuus eri käyttökohteisiin vaihtelee suuresti. Tyypillinen kaksiulotteista aluetta kuvaamaan käytetty rakenne on tasaisesti jaettu ruudukko, jossa alue on jaettu pysty- ja vaakasuunnassa kaikkialta yhtä suuriin neliön muotoisiin osiin. Tasaisesti jaettu ruudukko ei kuitenkaan ole ainoa tapa esittää ja jakaa alue, vaan sille on olemas-sa useita vaihtoehtoja, joilla on siihen nähden erilaisia hyöty- ja haittapuolia.

Tässä tutkimuksessa esitellään lyhyesti nelipuu käsitteenä ja siitä kehitetyn nelipuutietorakenteen eri tyyppejä ja käyttökohteita. Tutkimuksessa esitellään lähteisiin pohjautuen kolme versiota nelipuutietorakenteesta toimintaperiaatteineen ja annetaan lyhyt esimerkki ohjelmallisesti toteutetusta nelipuutietorakenteesta. Lisäksi esitellään kolme kirjallisuudessa esiintyvää kuvausta nelipuun toiminnasta käytännön sovelluksissa: hiukkasten liikkeen simuloinnissa, tsunamin mallinnuksessa ja ympäristön mallinnuksessa. Nelipuun soveltuvuutta, sen etuja ja siitä aiheutuvia haittoja arvioidaan kussakin käyttötarkoituksessa lähdetietojen pohjalta ja pyritään muodostamaan laajempi kuva siitä, millaisiin käyttötarkoituksiin nelipuu soveltuu hyvin. Arvioiden perusteella todetaan nelipuulla olevan selkeitä etuja kaksiulotteisen alueen kuvauksessa ja liikkeen mallinnuksessa, varsinkin kun tarkastelu halutaan kohdentaa johonkin osaan alueesta. Nelipuun etujen todetaan liittyvän sen mahdollistamaan mukautuvaan alueen jakamiseen ja vähäiseen tilankäyttöön. Nelipuun haittapuoliksi arvioidaan sen usein monimutkainen toteutus ja sen nopean käsittelyn vaatima suuri suorituskyky.