Quadtree.....

[traceygj]

Hi im kind of new too this, but im using the quadtree data structure for a project that i am working on. I am using this to recursively partition an image depending on the levels of pixel variance in selected regions. I am encountering problems when trying to partition groups of regions and was wondering if anyone knows much about the quadtree. I have never used it in a program before and cannot find any implementations of help on the net. I would be extremely gratefull for any help.

Thanks.

[RedSon]

Have you read the article on wikipedia? http://en.wikipedia.org/wiki/Quadtree

[traceygj]

Hi, yeah i have looked at that. I know how it is supposed to work, but its the reursive bit that is bothering me, i can recursively partition regions in one direction (eg, i can recursively partition the top left region of the image - and then the top left of that region - and the top left of that etc) . But the problem is trying to break down each region in all directions.

[RedSon]

Can you not break up your image into quadrants? Then recursively break those smaller images into quadrants? Try breaking it into quadrants one time and see if that works, then you can work out the recursive bit.

[traceygj]

Can you not break up your image into quadrants? Then recursively break those smaller images into quadrants? Try breaking it into quadrants one time and see if that works, then you can work out the recursive bit.

Yeah, i can break the image into quadrants, but when i call the method again recursively, it then keeps breaking the top left quadrant without reguard for the rest. Really bothering me as im normally good at java programming (its c# im using but almost identical) :-(.

[RedSon]

can you post your recursive routine? I suspect you need to call your routine 4 times one for each original quadrant and also one for each recursive quadrant.

[traceygj]

can you post your recursive routine? I suspect you need to call your routine 4 times one for each original quadrant and also one for each recursive quadrant.

I choped and chagned the code a little to make it a little easier to understand. Normally i have conditions to select which of the regions (I created a class called Iregion to represent each region) will be partitioned.

Sorry about the codes layout, im not sure how to post on these sites.

 public void partitionReg(Iregion r)
        {

            
                int wFrom = r.getW();
                int wTo = r.getX();
                int hFrom = r.getY();
                int hTo = r.getZ();
            

            //Drawing lines to show the four regions

                g.DrawLine(new Pen(Color.Red), (wFrom + wTo) / 2, hFrom, (wFrom + wTo) / 2, (hFrom + hTo) / 2);
                g.DrawLine(new Pen(Color.Red), (wFrom + wTo) / 2, (hFrom + hTo) / 2, (wFrom + wTo) / 2, hTo);
                g.DrawLine(new Pen(Color.Red), wFrom, (hFrom + hTo) / 2, (wFrom + wTo) / 2, (hFrom + hTo) / 2);
                g.DrawLine(new Pen(Color.Red), (wFrom + wTo) / 2, (hFrom + hTo) / 2, wTo, (hFrom + hTo) / 2);

                
            if(count !=4)
            {

                //Count represents the max depth.  
                count++;

                        
                        //Create the regions.
                        Iregion tl = new Iregion(wFrom, (wFrom + wTo) / 2, hFrom, (hTo + hFrom) / 2);
                        
                        partitionReg(tl);
                  
                        Iregion tr = new Iregion((wFrom + wTo) / 2, wTo, hFrom, (hTo + hFrom) / 2);
                        
                        partitionReg(tr);
                    
                    
                        Iregion bl = new Iregion(wFrom, (wFrom + wTo) / 2, (hTo + hFrom) / 2, hTo);
                        partitionReg(bl);
                      
                        Iregion br = new Iregion((wFrom + wTo) / 2, wTo, (hTo + hFrom) / 2, hTo);
                        partitionReg(br);
                      
            }
        
            }