TQuadTree2D.h

// TQuadTree2D.h: Schnittstelle für die Klasse TQuadTree2D.
//

#if !defined(AFX_TQUADTREE2D_H__FE2B3BFD_9805_4779_B341_2A52C07CBD52__INCLUDED_)
#define AFX_TQUADTREE2D_H__FE2B3BFD_9805_4779_B341_2A52C07CBD52__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include "TLinkedList.h"
#include "TKoo3d.h"
#include <qgl.h>
#include "TGeometryData.h"

class TGeometryData;

class TQuadTree2DNode
{
private:
        bool isLeave;
        TGeometryData* posData;
        TKoo3d<float> topLeft;
        TKoo3d<float> bottomRight;
        TKoo3d<int> quadInd[4];
        TQuadTree2DNode* childNodes[4];

        bool isWithin(TKoo3d<float>& k)
        {
                return (k.v[0]>topLeft.v[0])&&(k.v[1]>topLeft.v[1])&&
                        (k.v[0]<bottomRight.v[0])&&(k.v[1]<bottomRight.v[1]);
        }

public:
        TQuadTree2DNode(TGeometryData* posA,TQuadTree2DNode** childs=0,TKoo3d<int>* quad=0);
        virtual ~TQuadTree2DNode();
        TKoo3d<float> getTopLeft()
        {
                return topLeft;
        }
        TKoo3d<float> getBottomRight()
        {
                return bottomRight;
        }
        TLinkedList<TKoo3d<TKoo3d <int> > >* getTrisContaining(TKoo3d<float>& pos,TLinkedList<TKoo3d< TKoo3d<int> > >* aktList);

        void draw(TKoo3d<float>& pos, int layer)
        {
                if (layer<20&&isWithin(pos))
                {
                        
                        glBegin(GL_LINE_LOOP);
                        glColor3f(((float)layer)/3.0f,((float)layer)/2.0f,1);
                        glVertex3f(topLeft.v[0]*10,topLeft.v[1]*10,0);
                        glVertex3f(bottomRight.v[0]*10,topLeft.v[1]*10,0);
                        glVertex3f(bottomRight.v[0]*10,bottomRight.v[1]*10,0);
                        glVertex3f(topLeft.v[0]*10,bottomRight.v[1]*10,0);
                        
                        glEnd();
                        if (!isLeave)
                        
                                for (int i=0;i<4;i++)
                                        if (childNodes[i])
                                                childNodes[i]->draw(pos,layer+1);
                }
        }

};


class TQuadTree2D  
{
private:


        

        int xRes;
        int yRes;
        int translateToIndex(int x, int y)
        {
                return x+xRes*y;
        }
        TQuadTree2DNode** test;
        TQuadTree2DNode* root;
        TQuadTree2DNode* generateRootNode(int fromX, int toX, int fromY, int toY,TQuadTree2DNode** leaves,TGeometryData* posA);
public:
        TKoo3d<float> getBottomRight();
        TKoo3d<float> getTopLeft();
        TQuadTree2D(TGeometryData* posA, int resX, int resY);
        virtual ~TQuadTree2D();
        void draw()
        {
                glLineWidth(1.0);
                glColor3f(1,1,1);
                root->draw(TKoo3d<float> (6,8,0),0);
                //for (int i=(xRes-1)*100;i<(xRes-1)*200;i++)
                //      test[i]->draw(TKoo3d<float> (1,1,0),0);
        }

        TLinkedList<TKoo3d<TKoo3d<int> > >* getTrisContaining(TKoo3d<float>& pos,TLinkedList<TKoo3d<TKoo3d<int> > >* aktList); 

};

#endif // !defined(AFX_TQUADTREE2D_H__FE2B3BFD_9805_4779_B341_2A52C07CBD52__INCLUDED_)

---