-
Notifications
You must be signed in to change notification settings - Fork 9
Expand file tree
/
Copy pathQuadTree.h
More file actions
151 lines (145 loc) · 4.14 KB
/
QuadTree.h
File metadata and controls
151 lines (145 loc) · 4.14 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#pragma once
#include <list>
using std::list;
#define TREE_DEPTH 3
#define MIN_NODE_SIZE 0.1
#define SAFE_DELETE(p) do {delete (p); (p) = NULL;} while (false)
template<typename T> class QuadNode
{
protected:
float m_left, m_right, m_up, m_down;
list<T*> m_dataList;
QuadNode* m_child[4] = { NULL, NULL, NULL, NULL }; //0:LeftUp, 1:LeftDown, 2:RightUp, 3:RightDown
public:
QuadNode(float left, float right, float up, float down) :
m_left(left), m_right(right), m_up(up), m_down(down) {}
~QuadNode()
{
for (auto child : m_child)
SAFE_DELETE(child);
}
void SetDataList(list<T*> data) { m_dataList = data; }
//递归生成四叉树节点
void GenerateNode()
{
if (m_right - m_left > MIN_NODE_SIZE)
{
m_child[0] = new QuadNode<T>(m_left, (m_left + m_right) / 2.f, m_up, (m_up + m_down) / 2.f); //LU
m_child[1] = new QuadNode<T>(m_left, (m_left + m_right) / 2.f, (m_up + m_down) / 2.f, m_down); //LD
m_child[2] = new QuadNode<T>((m_left + m_right) / 2.f, m_right, m_up, (m_up + m_down) / 2.f); //RU
m_child[3] = new QuadNode<T>((m_left + m_right) / 2.f, m_right, (m_up + m_down) / 2.f, m_down); //RD
for (int i = 0; i < 4; i++)
{
list<T*> child_list = {};
for (list<T*>::iterator iter = m_dataList.begin(); iter != m_dataList.end();)
{
if ((*iter)->Contained(m_child[i]->m_left, m_child[i]->m_right, m_child[i]->m_up, m_child[i]->m_down))
{
child_list.push_back(*iter);
m_dataList.erase(iter++);
}
else
iter++;
}
if (child_list.empty())
{
delete m_child[i];
m_child[i] = NULL;
}
else
{
m_child[i]->SetDataList(child_list);
m_child[i]->GenerateNode();
}
}
}
}
float CalcLineFx(Point p, Vector d, Point s)
{
return d.y*s.x - d.x*s.y - p.x*d.y + p.y*d.x;
}
//判断射线与四叉树节点本身包围盒是否相交，用于剪枝
bool IntersectBound(Point p, Vector d)
{
//剪枝1
int flag = 0;
if(p.x < m_right && p.x > m_left && p.y < m_down && p.y > m_up) //p在节点内
return true;
if (p.x < m_left) flag |= 0x01;
else if (p.x < m_right) flag |= 0x0A;
else flag |= 0x0F;
if (p.y < m_up) flag |= 0x10;
else if (p.y < m_down) flag |= 0xA0;
else flag |= 0xF0;
switch (flag)
{
case 0x11: if (d.x <= 0.f || d.y <= 0.f) return false; break;
case 0x1A: if (d.y <= 0.f) return false; break;
case 0x1F: if (d.x > 0.f || d.y <= 0.f) return false; break;
case 0xA1: if (d.x <= 0.f) return false; break;
case 0xAA: return true;
case 0xAF: if (d.x > 0.f) return false; break;
case 0xF1: if (d.x <= 0.f || d.y > 0.f) return false; break;
case 0xFA: if (d.y > 0.f) return false; break;
case 0xFF: if (d.x > 0.f || d.y > 0.f) return false; break;
}
//剪枝2
if (CalcLineFx(p, d, { m_left, m_up })*CalcLineFx(p, d, { m_right, m_down }) < 0) return true;
if (CalcLineFx(p, d, { m_left, m_down })*CalcLineFx(p, d, { m_right, m_up }) < 0) return true;
return false;
}
//返回该射线相交的最近entity和距离
bool Intersect(Point p, Vector d, T* &ent_near, Point& inter, float& dist)
{
if (!IntersectBound(p, d)) return false;
for (auto ent : m_dataList) //首先获取该节点存储的entity中最近的交点
{
Point tmp_inter;
if (ent->Intersect(p, d, tmp_inter))
{
float tmp_dist = (tmp_inter - p).len();
if (dist > tmp_dist)
{
ent_near = ent;
dist = tmp_dist;
inter = tmp_inter;
}
}
}
for (int i = 0; i < 4; i++) //再递归比较子节点中的最近交点
{
QuadNode* node = m_child[i];
if (node) //由于在建树时已经进行了一次剪枝，因此一部分节点为空，不需要计算
{
T *tmp_ent;
Point tmp_inter;
float tmp_dist = 10.f;
if (node->Intersect(p, d, tmp_ent, tmp_inter, tmp_dist) && tmp_dist < dist)
{
ent_near = tmp_ent;
dist = tmp_dist;
inter = tmp_inter;
}
}
}
if (ent_near) return true;
else return false;
}
};
template<typename T> class QuadTree
{
protected:
QuadNode<T>* m_root; //根节点
public:
QuadTree(list<T*> data)
{
m_root = new QuadNode<T>(0.f, 1.f, 0.f, 1.f);
m_root->SetDataList(data);
m_root->GenerateNode();
}
void Intersect(Point p, Vector d, T* &ent, Point &inter)
{
float dist = 10.f;
m_root->Intersect(p, d, ent, inter, dist);
}
};