[LUGOS-PROG] 2D ploskev

[Andraz Tori]

precej easy... 
drevo, kjer ima vsak node 4 podnode, ki peljejo do (4 podkvadrante). v
zunanjih listih drevesa so linearni seznami predmetov.

s tem da globino pac dolocas tako da ce linearni seznam postane prevelik
ga spremenis v node in razdelis na 4 kose..

premikanje na majhne razdalje lahko potem opravljas precej ucinkovito
(ni se ti treba vracat do korena drevesa)

ce imas v dolocenih tockah ful (res ful) na gosto predmete, drugje pa
nic, potem lahko se nekaj optimizacij naredis, da drevo ni pregloboko
(skipanje vmesnih nodeov ki imajo le en podnode)...

seveda pa si pozabil nekaj podatkov: o kako velikih cifrah pravzaprav
govoris, ali so koodrinate plavajoca vejica ali integer, kaksni so rangi
koordinat.

in na koncu kaj sploh delas?

cao
andraz


Na 1074945780, 2004-01-24 ob 13:03, je polz napisal(a):
> A kdo izmed vas pozna kako podatkovno strukturo, ki bi zadoscala pogojem:
> 
> 1. predstavljala bo 2D plosco, na katero bodo postavljeni redki objekti
> 2. pogosta operacija bo premakni_objekt(dx, dy) , ki bo spremenila polozaj 
> objekta, pri cemer bo tak premik obicajno majhen
> 3. pogosta operacija bo najdi_objekte(x1, y1, x2, y2), ki bo nasel vse 
> objekte, ki so znotraj pravokotnika, katerega zgornji levi kot je (x1, y1), 
> spodnji desni pa (x2, y2).
> 
> Zanima me predvsem, ce je kaka taksna struktura splosno znana, njeno
> ime.
> Sploh fino bi bilo, ce bi bila ta rec ze scodana v C++.
>