4. Quad-Trees

Werner Van Belle¹ - werner@yellowcouch.org, werner.van.belle@gmail.com

1- Programming Technology Lab (PROG) Department of Computer Science (DINF) Vrije Universiteit Brussel (VUB); Pleinlaan 2; 1050 Brussel; Belgium

Abstract : Exercices on Quad-trees

Reference: Werner Van Belle; Quad-Trees;

Info

Quadtrees worden (werden??) gebruikt om 2dimensionale data op een compacte wijze te kunnen opslaan. Het idee is om het vlak dat gecompressed moet worden te splitsen in vier en elk egaal vlak te markeren als ‘egaal in die kleur’. Vlakken die zowat beide kleuren bevat worden verder gesplitst.

Oef1: Quadtree creeeren

Teken een lijn op het scherm (vga_drawline())
Creeer de quadtree van deze tekening.
Duid al de splitsingen aan in het wit zodat u een beeld hebt wat voor resultaat het algoritme geeft.

Bespreek de voor en nadelen van dit algoritme

Oef2: granulariteit

Bespreek in hoeverre de diepste splitsingen nog nodig zijn. Bereken op welke breedte we zowiezo mogen stoppen omdat we anders te veel data creeeren.

Oef3: Data opslag

Zorg dat je de gegeven quadtree zo compact mogelijk kan wegschrijven naar disk. Denk eerst grondig na over de datarepresentatie die je gaat gebruiken op het opslagmedium. Wat denkt u ervan om een systeem zoals bij heaps te gebruiken ?

Oef4: Balanceren

Is het mogelijk een quadtree te balanceren ? Welke criteria hanteer je ervoor ?

#include <vga.h>
#include <stdlib.h>

// als kleur == -1, node ; anders leaf
typedef struct quad { 
   int x1; int y1;
   int x2; int y2;
   int kleur;
   struct quad *lb; 
   struct quad *rb;
   struct quad *lo;
   struct quad *ro;
} *Quad;

int inrectangle(int x1, int y1, int x2, int y2);
void quadconstruct(Quad q);

void quadconstruct(Quad q)
{
   Quad lb,rb,lo,ro;
   int midx, midy;
   int x1 = q->x1, y1 = q->y1, x2 = q->x2, y2 = q->y2;
   // niet te klein ??
   if (x2<=x1) return;
   if (y2<=y1) return;
   // egaal ???
   q->kleur=inrectangle(x1, y1, x2, y2);
   if (q->kleur!=-1)
     {q->lb = q->rb = q->lo = q->ro = NULL;
     return;}
   // niet egaal -> creeeren + splitsen
   
   lb = (Quad) malloc(sizeof(struct quad));
   rb = (Quad) malloc(sizeof(struct quad));
   lo = (Quad) malloc(sizeof(struct quad));
   ro = (Quad) malloc(sizeof(struct quad));

   q->lb = lb; q->rb = rb; q->lo = lo; q->ro = ro;

   midx = (x2+x1) /2; 
   midy = (y2+y1) /2;
   lb->x1 = x1;       lb->y1=y1;      lb->x2=midx ;  lb->y2=midy;
   rb->x1 = midx+1;   rb->y1=y1;      rb->x2=x2;     rb->y2=midy;
   lo->x1 = x1;       lo->y1=midy+1 ; lo->x2=midx ;  lo->y2=y2;
   ro->x1 = midx+1;   ro->y1=midy+1 ; ro->x2=x2 ;    ro->y2=y2;
   
   quadconstruct(q->lb);
   quadconstruct(q->rb);
   quadconstruct(q->lo);
   quadconstruct(q->ro);
   
   vga_setcolor(5);
   vga_drawline(x1,midy,x2,midy);
   vga_drawline(midx,y1,midx,y2);
}

int inrectangle(int x1, int y1, int x2, int y2)
{
   int i,j,kl;
   kl=graph_mem[x1+y1*0];
   for(i=y1 ; i <= y2 ; ++i)
     for(j=x1 ; j <= x2 ; ++j)
       if (graph_mem[i*0 +j]!=kl)
	 return -1;
   return kl;
}

void main(void)
{
   Quad q;
   
   vga_setmode(G320x200x256);
   vga_setcolor(2);
   vga_drawline(0, 0, 9, 9);
   vga_drawline(5, 0, 0, 0);
   q->x1 = 0; q->y1 = 0; q->x2 = 9; q->y2 = 9;
   quadconstruct(q);
   sleep(0);
}

http://werner.yellowcouch.org/
werner@yellowcouch.org