Добавил:
Studfiles2
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:Региональный поиск метод дерева регионов / Source / Trees
.cpp#include "StdAfx.h"
#include "Trees.h"
template<class NodeType>
BinaryTree<NodeType>::BinaryTree(NodeType node, BinaryTree<NodeType>* left,
BinaryTree<NodeType>* right) :
Left(left), Right(right), NodeValue(node)
{
}
/*KLPIterator<NodeType>& KLPIterator<NodeType>::operator++()
{
return this;
}*/
RegionTree::RegionTree(const std::vector<Point>& points) : Ys(points), Xs(points), NodeCount(0)
{
std::sort(Ys.begin(), Ys.end(), OrderByY());
std::sort(Xs.begin(), Xs.end(), OrderByX());
SearchTree = ConsRegionTree(1, points.size()+1, std::list<Point>(Ys.begin(), Ys.end()));
}
BinaryTree<RegionTreeNode>* RegionTree::ConsRegionTree(int l, int r, std::list<Point> allp)
{
BinaryTree<RegionTreeNode>* result;
if(r-l==1) result=new BinaryTree<RegionTreeNode>(RegionTreeNode(l,r,allp));
else
{
int c = (l+r)/2;
ASSERT((c-l)>0);
ASSERT((r-c)>0);
std::list<Point> left;
std::list<Point> right;
ASSERT((c-1)>=0 && (c-1)<Xs.size());
int central = Xs[c-1].first;
std::list<Point>::iterator i=allp.begin();
while(i!=allp.end())
{
if(i->first<central)
left.push_back(*i);
else
right.push_back(*i);
i++;
}
result=new BinaryTree<RegionTreeNode>(RegionTreeNode(l,r,allp),
ConsRegionTree(l,c,left),
ConsRegionTree(c,r,right));
}
NodeCount++;
return result;
}
std::list<Point> RegionTree::Search(int x0, int y0, int x1, int y1)
{
this->x0=1;
this->x1=1;
int i=0;
while(Xs[i].first<x0)
{
this->x0++;
i++;
if(i==Xs.size()) break;
}
i=0;
while(Xs[i].first<x1)
{
this->x1++;
i++;
if(i==Xs.size()) break;
}
this->y0=y0;
this->y1=y1;
Result.clear();
ClearFlags(SearchTree);
SearchSteps.clear();
if(this->x0<this->x1) Search(SearchTree);
return Result;
}
void RegionTree::Search(BinaryTree<RegionTreeNode>* t)
{
t->GetNodeValue().SetOnWay(true);
int b=t->GetNodeValue().GetB();
int e=t->GetNodeValue().GetE();
int c=(b+e)/2;
if(x0<=b && e<=x1)
{
//это узел отнесения
t->GetNodeValue().SetFlag(true);
SearchSteps.push_back(SearchStep(t, SearchStep::NodeFound));
Point p1(0,y0);
std::vector<Point>::const_iterator i1=std::lower_bound(t->GetNodeValue().GetPoints().begin(),
t->GetNodeValue().GetPoints().end(), p1, OrderByY());
std::vector<Point>::const_iterator i2 = i1;
while(i2!=t->GetNodeValue().GetPoints().end())
if(y1>=i2->second) i2++; else break;
t->GetNodeValue().SetFirstAndLastPoint(i1, i2);
int d = std::distance(i1,i2);
if(d>0)
{
SearchSteps.push_back(SearchStep(t, SearchStep::BinarySearch1));
if(d>1)
{
SearchSteps.push_back(SearchStep(t, SearchStep::BinarySearch2));
if(d>2)
SearchSteps.push_back(SearchStep(t, SearchStep::SelectPoints));
}
}
std::copy(i1, i2, std::back_inserter(Result));
}
else
{
SearchSteps.push_back(SearchStep(t, SearchStep::SearchNode));
if(x0<c && t->GetLeftSubTree()) Search(t->GetLeftSubTree());
if(c<x1 && t->GetRightSubTree()) Search(t->GetRightSubTree());
}
}
void RegionTree::ClearFlags(BinaryTree<RegionTreeNode>* t)
{
if(t)
{
t->GetNodeValue().SetFlag(false);
t->GetNodeValue().SetOnWay(false);
ClearFlags(t->GetLeftSubTree());
ClearFlags(t->GetRightSubTree());
}
}
Соседние файлы в папке Source