Опытный
Профиль
Группа: Участник
Сообщений: 829
Регистрация: 8.6.2011
Репутация: нет
Всего: нет
|
| Код |
// QuadTree.h: interface for the TreeNode class.
#define NUM_LINES_THRESHOLD 5 //если больше этого кол-ва линий в ноде то делим опять
#define QUAD_MIN_SIZE 100 // минимальный размер квадрата нода
using namespace std;
class line
{
public:
CPoint p1;
CPoint p2;
};
class TreeNode
{
public:
TreeNode* child[4];
int x;
int y;
int w;
int h;
vector<line> lines;
TreeNode(int x_in, int y_in, int width, int height)
{
x=x_in;
y=y_in;
w=width;
h=height;
}
};
//пересечение прямоугольника с отрезком(как попарное пересечение с 4-мя отрезками)
bool IsSegmentCross(CPoint p11, CPoint p12, int x,int y,int w, int h)
{
//возможно проставить тут легкие условия чтобы сразу отмести сложные вычисления
//имеем 4 отрезка из прямоугольника
CPoint p21;
CPoint p22;
//top
p21.x=x;
p21.y=y;
p22.x=x+w;
p22.y=y+h;
// знаменатель
double Z = (p12.y-p11.y)*(p21.x-p22.x)-(p21.y-p22.y)*(p12.x-p11.x);
// если знаменатель = 0, прямые параллельны
if (Z==0) //тем более что сравнение дабла с 0 некоректно
{
return false;
}
// числитель 1
double Ca = (p12.y-p11.y)*(p21.x-p11.x)-(p21.y-p11.y)*(p12.x-p11.x);
// числитель 2
double Cb = (p21.y-p11.y)*(p21.x-p22.x)-(p21.y-p22.y)*(p21.x-p11.x);
double Ua = Ca/Z;
double Ub = Cb/Z;
// если 0<=Ua<=1 и 0<=Ub<=1, точка пересечения в пределах отрезков
if( (0 <= Ua)&&(Ua <= 1)&&(0 <= Ub)&&(Ub <= 1) )
return true;
//right
p21.x=x;
p21.y=y;
p22.x=x+w;
p22.y=y+h;
Z = (p12.y-p11.y)*(p21.x-p22.x)-(p21.y-p22.y)*(p12.x-p11.x);
if (Z==0)
{
return false;
}
Ca = (p12.y-p11.y)*(p21.x-p11.x)-(p21.y-p11.y)*(p12.x-p11.x);
Cb = (p21.y-p11.y)*(p21.x-p22.x)-(p21.y-p22.y)*(p21.x-p11.x);
Ua = Ca/Z;
Ub = Cb/Z;
// если 0<=Ua<=1 и 0<=Ub<=1, точка пересечения в пределах отрезков
if( (0 <= Ua)&&(Ua <= 1)&&(0 <= Ub)&&(Ub <= 1) )
return true;
//bottom
p21.x=x;
p21.y=y;
p22.x=x+w;
p22.y=y+h;
Z = (p12.y-p11.y)*(p21.x-p22.x)-(p21.y-p22.y)*(p12.x-p11.x);
if (Z==0)
{
return false;
}
Ca = (p12.y-p11.y)*(p21.x-p11.x)-(p21.y-p11.y)*(p12.x-p11.x);
Cb = (p21.y-p11.y)*(p21.x-p22.x)-(p21.y-p22.y)*(p21.x-p11.x);
Ua = Ca/Z;
Ub = Cb/Z;
// если 0<=Ua<=1 и 0<=Ub<=1, точка пересечения в пределах отрезков
if( (0 <= Ua)&&(Ua <= 1)&&(0 <= Ub)&&(Ub <= 1) )
return true;
//left
p21.x=x;
p21.y=y;
p22.x=x+w;
p22.y=y+h;
Z = (p12.y-p11.y)*(p21.x-p22.x)-(p21.y-p22.y)*(p12.x-p11.x);
if (Z==0)
{
return false;
}
Ca = (p12.y-p11.y)*(p21.x-p11.x)-(p21.y-p11.y)*(p12.x-p11.x);
Cb = (p21.y-p11.y)*(p21.x-p22.x)-(p21.y-p22.y)*(p21.x-p11.x);
Ua = Ca/Z;
Ub = Cb/Z;
// если 0<=Ua<=1 и 0<=Ub<=1, точка пересечения в пределах отрезков
if( (0 <= Ua)&&(Ua <= 1)&&(0 <= Ub)&&(Ub <= 1) )
return true;
return false;
}
TreeNode* BuildNode(TreeNode* node, TreeNode* nParent, int index)
{
node = new TreeNode(0, 0, 0, 0);
int w=nParent->w/2;
int h=nParent->h/2;
int x=nParent->x;
int y=nParent->y;
switch(index)
{
case 0: // Top left
node->x = x;
node->y = y;
break;
case 1: // Top right
node->x = x + w;
node->y = y;
break;
case 2: // Bottom right
node->x = x + w;
node->y = y + h;
break;
case 3: // Bottom left
node->x = x;
node->y = y + h;
break;
}
node->w=w;
node->h=h;
const int numParentLines = nParent->lines.size();
int IntersectionsCount=0;
switch(index)
{
case 0:// Top left
for(int i = 0; i < numParentLines; ++i)
{
if(IsSegmentCross(nParent->lines[i].p1, nParent->lines[i].p2, node->x,node->y,node->w,node->h))
{
++IntersectionsCount;
node->lines.push_back(nParent->lines[i]);
}
}
break;
case 1:// Top right
for(int i = 0; i < numParentLines; ++i)
{
if(IsSegmentCross(nParent->lines[i].p1, nParent->lines[i].p2, node->x,node->y,node->w,node->h))
{
++IntersectionsCount;
node->lines.push_back(nParent->lines[i]);
}
}
break;
case 2:// Bottom right
for(int i = 0; i < numParentLines; ++i)
{
if(IsSegmentCross(nParent->lines[i].p1, nParent->lines[i].p2, node->x,node->y,node->w,node->h))
{
++IntersectionsCount;
node->lines.push_back(nParent->lines[i]);
}
}
break;
case 3:// Bottom left
for(int i = 0; i < numParentLines; ++i)
{
if(IsSegmentCross(nParent->lines[i].p1, nParent->lines[i].p2, node->x,node->y,node->w,node->h))
{
++IntersectionsCount;
node->lines.push_back(nParent->lines[i]);
}
}
break;
}
return node;
}
void BuildQuadTree(TreeNode* node)
{
if(node->lines.size() > NUM_LINES_THRESHOLD&&
node->w > QUAD_MIN_SIZE&&
node->h > QUAD_MIN_SIZE) //ограничение на кол-во линий + на размер ячейки
{
for(int i = 0; i < 4; ++i)
{
TreeNode* nodeIn = new TreeNode(0, 0, 0, 0);
nodeIn = BuildNode(node->child[i], node, i);
BuildQuadTree(nodeIn);
}
}
return vec_test;
}
//пересечение 2-х прямоугольников
bool RectIntersection(int x1,int y1,int w1, int h1, int x2, int y2, int w2,int h2)
{
if (min (x1+w1, x2+w2) > max (x1, x2) && min (y1, y2) > max (y1+h1, y2+h2) )
return true;
else
return false;
}
//извлечение в список всех линий для вывода по прямоугольнику view'a
vector<line> GetLinesClipRegion(int x, int y, int w, int h, TreeNode* rootNode)
{
vector<TreeNode*> NodeList;
vector<line> vec_lines;
NodeList.push_back(rootNode);
while(NodeList.size()!=0)
{
TreeNode* temp= NodeList.back();
NodeList.pop_back();
for (int i=0;i<4;++i)
{
if(temp->child[i]!=NULL) // не срабатывает проверка на нул
{
int x_t=temp->child[i]->x;
int y_t=temp->child[i]->y;
int w_t=temp->child[i]->w;
int h_t=temp->child[i]->h;
if(RectIntersection(x,y,w,h,x_t,y_t,w_t,h_t))
{
NodeList.push_back(temp->child[i]);
}
}
else
{
for(unsigned int k=0;k<temp->lines.size();++k)
{
vec_lines.push_back(temp->lines[k]);
}
}
}
}
return vec_lines;
}
|
вроде дерево нормально собирается , но почему то ссылки не проставляются и if(temp->child[i]!=NULL) не срабатывает. вызываю в коде так. | Код |
TreeNode* rootNode = new TreeNode(0, 0, w, h);
rootNode->lines=vec_lines;
BuildQuadTree(rootNode);
vector<line> vec_test= GetLinesClipRegion(0,0,1000,1000,rootNode);
|
|
Quad-tree 
Загрузка ...
