Storer

Yleistä

Storer on apuluokka, jonka tehtävänä on tallettaa Positioned-rajapinnan täyttäviä olioita, eli olioita, joilla on 2-ulotteinen keskipiste, ja osata kertoa tehokkaasti, mikä piste on lähimpänä annettua pistettä kutsuttaessa metodia closestTo(Positioned). Esimerkiksi jos meillä on pisteet (1, 3), (6, 6) ja (2, 9) talletettuna Storeriin, voimme tehdä kutsun myStorer.closestTo( 2.0, 2.0 ). Tällöin Storer palauttaa objektin, joka sijaitsi kohdassa (1, 3).

Käyttötarkoitus

Algoritmit, joita ohjelmassa käytetään, pystytään toteuttamaan helposti tällaista rajapintaa käyttäen, ja samalla ohjelmasta tulee nopeampi, sillä Storerin hakuaika on logaritminen.

Käytetty tietorakenne

Storer perustuu binääripuurakenteeseen, jossa tietty solmu kuvaa tiettyä graafista aluetta. Jokainen askel alaspäin puussa jakaa alueen kahtia vuorotellen pysty- ja vaakasuorassa.

Algoritmit

Pisteen lisääminen

Etsitään se solmu, jonka alueen sisällä lisättävä piste on. Jos tämä solmu on tyhjä, lisätään piste siihen. Muussa tapauksessa tarkistetaan onko solmun sisältämän pisteen etäisyys lisättävästä pisteestä tietyn epsilonin sisällä, ja jos on, tallennetaan se samaan solmuun sen tiedon kanssa, että solmussa on useampia pisteitä. Jos pisteet ovat eri paikoissa, jatketaan seuraavasti: Jos hakuaskelten määrä oli parillinen, jaetaan solmun alue kahtia pystysuorassa, muuten vaakasuorassa. Jos solmun aiemmin sisältämä piste tämän jälkeen on samassa puoliskossa kuin lisättävä piste, jaetaan solmu uudestaan tällä kertaa eri suunnassa, ja näin edespäin rekursiivisesti, kunnes pisteet ovat eri solmuissa.

Hakualgoritmi

Lähimmän pisteen haku tapahtuu seuraavasti: Etsitään se solmu, jonka alueelle lisättävä piste kuuluu. Tämä jälkeen otetaan solmun viereiset solmut (viereiset solmut tallennetaan adjacents-listaan kullekin solmulle, ja niitä voi olla mielivaltainen määrä), ja tutkitaan yksi kerrallaan mikä näiden kaikkien solmujen pisteistä on lähinnä etsittävää pistettä.

Halkaisualgoritmi

Solmun halkaiseminen ei ole triviaalia, koska pisteen on tallennettava kaikki pisteet, jotka ovat sen ympäristössä. Näin ollen solmua halkaistaessa on ensin tutkittava mitkä aiemmista viereisistä solmuista ovat yhä sen vieressä, ja tallennettava nämä solmut adjacents-listaan. Tämän jälkeen on viereisille solmuille kerrottava, että niiden viereinen solmu on muuttunut, tai lisättävä molemmat halkaistun solmun puoliskot niiden adjacent-listoihin riippuen niiden tarkasta sijainnista. On triviaalia selvittää mitkä solmujen alueet ovat vierekkäin, joskin suhteellisen työlästä, joten sitä ei liene tarpeen selittää.