Скачиваний:
13
Добавлен:
01.05.2014
Размер:
7.75 Кб
Скачать
#include <math.h>

#include "stdafx.h"
#include "MainStructures.h"
#include "QTreeView.h"

///////////////////////////////////////////////////////////
//Описание вспомогательных функций
///////////////////////////////////////////////////////////
//определяет, налагаются ли проекции двух прямоугольников
//по координате
BOOL OverlappingExtent(Rect &a,Rect &b,int i)
{
	BOOL a_,b_,c_,d_,e_,f_,g_;
	a_=(a.sw[i]<b.sw[i])||(a.sw[i]==b.sw[i]);
	b_=(b.sw[i]<a.ne[i])||(b.sw[i]==a.ne[i]);
	c_=(b.sw[i]<a.sw[i])||(b.sw[i]==a.sw[i]);
	d_=(a.sw[i]<b.ne[i])||(a.sw[i]==b.ne[i]);
	e_=a_&&b_;
	f_=c_&&d_;
	g_=e_||f_;
	
	return g_;
}
//определяет, пересекаются ли два прямоугольника
BOOL Intersect(Rect &a,Rect &b)
{
	return (OverlappingExtent(a,b,0) &&
			OverlappingExtent(a,b,1));
};


///////////////////////////////////////////////////////////
//Описание методов класса Grid
///////////////////////////////////////////////////////////
//конструкторы
Grid::Grid(void):
	m(0),m_cellSize(0),m_pGrid(NULL)
{
}

Grid::Grid(int domainSize,List s,int n,int _m):
	m(_m),m_cellSize(domainSize/_m)

{
	m_pGrid=new List**[m];
	for(int i=0;i<m;i++)
	{
		m_pGrid[i]=new List*[m];

		for(int j=0;j<m;j++) 
			m_pGrid[i][j]=new List;
	}
	for(i=0;i<n;i++)
	{
		int a=int((s[i]).x/m_cellSize);
		int b=int((s[i]).y/m_cellSize);
		if ((a<m)&&(b<m)) m_pGrid[a][b]->Append(ELEMENT(s[i]));
	}
}

//деструктор
Grid::~Grid(void) 
{
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<m;j++)
		{
			m_pGrid[i][j]->Last();
			while (m_pGrid[i][j]->Lenght()>0)
			 m_pGrid[i][j]->Remove();
			delete m_pGrid[i][j];
		}
		delete m_pGrid[i];
	}
	delete m_pGrid;
}

//создание сетки (инициализация новыми параметрами)
void Grid::Create(int domainSize,List s,int n,int _m)
{
	//удаление предыдущей структуры
	for(int i=0;i<m;i++)
	{
		for(int j=0;j<m;j++)
		{
			m_pGrid[i][j]->Last();
			while (m_pGrid[i][j]->Lenght()>0)
			 m_pGrid[i][j]->Remove();
			delete m_pGrid[i][j];
		}
		delete m_pGrid[i];
	}
	delete m_pGrid;

	//построение новой структуры
	m=_m;
	m_cellSize=domainSize/m;
	m_pGrid=new List**[m];
	for(i=0;i<m;i++)
	{
		m_pGrid[i]=new List*[m];

		for(int j=0;j<m;j++) 
			m_pGrid[i][j]=new List;
	}
	for(i=0;i<n;i++)
	{
		int a=int((s[i]).x/m_cellSize);
		int b=int((s[i]).y/m_cellSize);
		if ((a<m)&&(b<m)) m_pGrid[a][b]->Append(ELEMENT(s[i]));
	}
};

//запрос по области
List *Grid::RangeQuery(Rect &r)
{
	List *result=new List;
	int ilimit=int(r.ne.x/m_cellSize);
	int jlimit=int(r.ne.y/m_cellSize);
	for(int i=int(r.sw.x/m_cellSize);i<=ilimit;i++)
		for(int j=int(r.sw.y/m_cellSize);j<=jlimit;j++)
		{
			List *pts=m_pGrid[i][j];
			for(pts->First();!pts->isHead();pts->Next())
			{
				ELEMENT *p=pts->Val();
				if ((p->x<=r.ne.x)&&(p->x>=r.sw.x) &&
			        (p->y<=r.ne.y)&&(p->y>=r.sw.y))
					result->Append(ELEMENT(*p));
			}
		}

	return result;
}


///////////////////////////////////////////////////////////
//Описание методов класса QTreeNode
///////////////////////////////////////////////////////////
//конструкторы
QTreeNode::QTreeNode(List *_pts):
	pts(_pts),m_size(_pts->Lenght())
{
	for(int i=0;i<4;i++)
		child[i]=NULL;
}

QTreeNode::QTreeNode(void):
	pts(NULL),m_size(0)
{
	for(int i=0;i<4;i++)
		child[i]=NULL;
}

QTreeNode::~QTreeNode()
{
	if(isExternal())
	{
		pts->Last();
		while(pts->Lenght()>0) pts->Remove();
		delete pts;
	}
		else for(int i=0;i<4;i++) delete child[i];
}

//запрос по области
List *QTreeNode::RangeQuery(Rect &r,Rect &span,int &level,const int Index,
							Rect &curRange,ELEMENT &curPoint)
{
	List *result=new List;
	if (level==Index)
		  {
			  curRange=span;
			  curPoint.x=-1;
			  curPoint.y=-1;
			  level++;
			  return result;
		  }
	if (level>Index) return result;

	level++;
	
	if (!Intersect(r,span))
	{
		return result;
	}
	 else 
	{
		if (isExternal())
		{ 
		  for(pts->First();!pts->isHead();pts->Next())
		  {
		    ELEMENT *p=pts->Val();
			if (level==Index)
			{
			  curRange=span;
			  curPoint=*p;
			  level++;
			  return result;
			}
			level++;
			if ((p->x<=r.ne.x)&&(p->x>=r.sw.x) &&
			    (p->y<=r.ne.y)&&(p->y>=r.sw.y))
				result->Append(ELEMENT(*p));
		  }//end of for
		}//end of if
		 else
		{
			for(int i=0;i<4;i++)
			{
				List *l=child[i]->RangeQuery(r,Quadrant(span,i),level,
				        				     Index,curRange,curPoint);
				for(l->First();!l->isHead();l->Next())
				result->Append(ELEMENT(*(l->Val())));
			}
		}
	 }
	
	return result;
}

//вычисление квадранта, накрываемого данным узлом
Rect QTreeNode::Quadrant(Rect &s,int i)
{
	ELEMENT c((s.sw.x+s.ne.x)/2,(s.sw.y+s.ne.y)/2);
	switch (i)
	{
	case 0: return Rect(c,s.ne);
	case 1: return Rect(ELEMENT(c.x,s.sw.y),ELEMENT(s.ne.x,c.y));
	case 2: return Rect(s.sw,c);
	case 3: return Rect(ELEMENT(s.sw.x,c.y),ELEMENT(c.x,s.ne.y));
	default: DBG("default case?"); return Rect(Point(), Point());
	}
}

//является ли текущий узел внешним
int QTreeNode::isExternal()
{
	return (pts!=NULL);
}

//отображение квадранта, накрываемого данным узлом
void QTreeNode::Draw(Rect& r,CDC* pDC)
{
	if(isExternal()) 
		pDC->Rectangle((int)r.sw.x,(int)r.ne.y,
					   (int)r.ne.x,(int)r.sw.y);
	 else
		for(int i=0;i<4;i++) 
			child[i]->Draw(Quadrant(r,i),pDC);
}


///////////////////////////////////////////////////////////
//Описание методов класса QTree
///////////////////////////////////////////////////////////
//конструкторы
QTree::QTree(void):
	m_root(NULL),m_domain(Rect(ELEMENT(0,0),ELEMENT(0,0)))
{
}

QTree::QTree(Grid &G,int M,int D,List &steps):
	m_root(BuildQTree(G,M,D,0,0,G.m-1,0,G.m-1,steps)),
	m_domain(Rect(ELEMENT(0,0),ELEMENT(G.m*G.m_cellSize,G.m*G.m_cellSize)))
{
}

//деструктор
QTree::~QTree()
{
	delete m_root;
}

//создание новой структуры дерева
void QTree::Create(Grid &G,int M,int D,List &steps)
{
	//удаление предыдущей структуры
	delete m_root;

	//создание новой структуры
	m_root=BuildQTree(G,M,D,0,0,G.m-1,0,G.m-1,steps);
	m_domain=Rect(ELEMENT(0,0),ELEMENT(G.m*G.m_cellSize,G.m*G.m_cellSize));
}

//осуществляет построение дерева
QTreeNode *QTree::BuildQTree(Grid &G,int M,int D,int level,int imin,int imax,int jmin,int jmax,List &steps)
{
	steps.Append(ELEMENT(imin,jmin));
	steps.Append(ELEMENT(imax,jmax));

	if (imin==imax)
	{
		QTreeNode *q=new QTreeNode(G.m_pGrid[imin][jmin]);
		G.m_pGrid[imin][jmin]=new List;
		return q;
	}	
		else
	{
		QTreeNode *p=new QTreeNode;
		int imid=(imin+imax)/2;
		int jmid=(jmin+jmax)/2;
		p->child[0]=BuildQTree(G,M,D,level+1,imid+1,imax,jmid+1,jmax,steps);
		p->child[1]=BuildQTree(G,M,D,level+1,imid+1,imax,jmin,jmid,steps);
		p->child[2]=BuildQTree(G,M,D,level+1,imin,imid,jmin,jmid,steps);
		p->child[3]=BuildQTree(G,M,D,level+1,imin,imid,jmid+1,jmax,steps);
		
		for(int i=0;i<4;i++) p->m_size+=p->child[i]->m_size;
		if ((p->m_size<=M)||(level>=D))
		{
			p->pts=new List;
			for(int j=0;j<4;j++)
			{
				for(p->child[j]->pts->First();
				   !p->child[j]->pts->isHead();
				    p->child[j]->pts->Next())
					p->pts->Append(ELEMENT(*(p->child[j]->pts->Val())));
				delete p->child[j];
				p->child[j]=NULL;
			}
			steps.Append(ELEMENT(imin,jmin));
			steps.Append(ELEMENT(imax,jmax));
		};
		
		return p;
	}
}

//осуществляет запрос по области
List *QTree::RangeQuery(Rect &r,int &level,const int Index,
						Rect &curRange,ELEMENT &curPoint)
{
	return m_root->RangeQuery(r,m_domain,level,Index,
							  curRange,curPoint);
}

//отображение сетки построенного дерева
void QTree::DrawQTree(CDC* pDC)
{
	m_root->Draw(m_domain,pDC);
}
Соседние файлы в папке src