-
Notifications
You must be signed in to change notification settings - Fork 141
Expand file tree
/
Copy pathQTree.h
More file actions
114 lines (102 loc) · 2.82 KB
/
QTree.h
File metadata and controls
114 lines (102 loc) · 2.82 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
/////////////////////////////////////////////
//QTree.h the header of quadtree class
//Description: This class is a general component that can make quadtree support for other components
////////////////////////////////////////////
//The contents of this file are subject to the Mozilla Public License Version 1.1 (the "License");
//you may not use this file except in compliance with the License. You may obtain a copy of the License at
//http://www.mozilla.org/MPL/
//Software distributed under the License is distributed on an "AS IS" basis, WITHOUT WARRANTY OF
//ANY KIND, either express or implied. See the License for the specific language governing rights and
//limitations under the License.
//
// The original Author is Neio([email protected]) and released as public domain in July 2009 to be a part of MapWinGIS.
// The contributors should list themselves and their modifications here.
//////////////////////////////////////////////////////////
#pragma once
using namespace std;
#define MAX_LEAF_NODES 100
class QTreeExtent
{
public:
double left;
double right;
double top;//max
double bottom;//min
public:
QTreeExtent() {
this->left = this->right = this->top = this->bottom = 0.0;
};
QTreeExtent(double left, double right, double top, double bottom)
{
// Ensure the extent has a width > 0
if (abs(left - right) < 0.0005) {
left -= 0.00025;
right += 0.00025;
}
// Ensure the extent has a height > 0
if (abs(top - bottom) < 0.0005) {
bottom -= 0.00025;
top += 0.00025;
}
this->left = left;
this->right = right;
this->top = top;
this->bottom = bottom;
}
bool Contain(const QTreeExtent& o)
{
return (left <= o.left
&& right >= o.right
&& top >= o.top
&& bottom <= o.bottom);
}
bool ContainIn(const QTreeExtent& o)
{
return (left >= o.left
&& right <= o.right
&& top <= o.top
&& bottom >= o.bottom);
}
bool IntersectIn(QTreeExtent& o)
{
return !(o.right < left
|| o.left > right
|| o.top < bottom
|| o.bottom > top
);
}
QTreeExtent& operator= (const QTreeExtent& o)
{
if (this == &o)
{
return *this;
}
this->left = o.left;
this->right = o.right;
this->top = o.top;
this->bottom = o.bottom;
return *this;
}
};
struct QTreeNode
{
QTreeExtent Extent;
int index;//index for storaged element
};
class QTree
{
private:
QTree* LT, * RT, * LB, * RB; //Four corners
vector<QTreeNode*> nodes; //nodes
QTreeExtent extent;
void Regenerate();
bool isFull;
bool regenerating;
public:
QTree() { LT = RT = LB = RB = nullptr; isFull = false; regenerating = false; }
QTree(QTreeExtent);
~QTree(void);
void AddNode(const QTreeNode&);
bool RemoveNode(int index);//return if success
vector<int> GetNodes(QTreeExtent queryExtent);//Query Nodes
};