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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
|
/**********************************************************************
* $Id: Quadtree.cpp,v 1.15 2004/12/08 13:54:43 strk Exp $
*
* GEOS - Geometry Engine Open Source
* http://geos.refractions.net
*
* Copyright (C) 2001-2002 Vivid Solutions Inc.
*
* This is free software; you can redistribute and/or modify it under
* the terms of the GNU Lesser General Public Licence as published
* by the Free Software Foundation.
* See the COPYING file for more information.
*
**********************************************************************/
#include <geos/indexQuadtree.h>
#include <geos/util.h>
#ifndef DEBUG
#define DEBUG 0
#endif
namespace geos {
/*
* Ensure that the envelope for the inserted item has non-zero extents.
* Use the current minExtent to pad the envelope, if necessary.
* Can return a new Envelope or the given one.
*/
Envelope* Quadtree::ensureExtent(const Envelope *itemEnv,double minExtent) {
//The names "ensureExtent" and "minExtent" are misleading -- sounds like
//this method ensures that the extents are greater than minExtent.
//Perhaps we should rename them to "ensurePositiveExtent" and "defaultExtent".
//[Jon Aquino]
double minx=itemEnv->getMinX();
double maxx=itemEnv->getMaxX();
double miny=itemEnv->getMinY();
double maxy=itemEnv->getMaxY();
// has a non-zero extent
if (minx!=maxx && miny!=maxy) return (Envelope *)itemEnv;
// pad one or both extents
if (minx==maxx) {
minx=minx-minExtent/2.0;
maxx=minx+minExtent/2.0;
}
if (miny==maxy) {
miny=miny-minExtent/2.0;
maxy=miny+minExtent/2.0;
}
Envelope *newEnv = new Envelope(minx, maxx, miny, maxy);
return newEnv;
}
/**
* Constructs a Quadtree with zero items.
*/
Quadtree::Quadtree(){
minExtent=1.0;
root=new QuadTreeRoot();
}
Quadtree::~Quadtree(){
for (unsigned int i=0; i<newEnvelopes.size(); i++)
delete newEnvelopes[i];
delete root;
}
/**
* Returns the number of levels in the tree.
*/
int Quadtree::depth() {
//I don't think it's possible for root to be null. Perhaps we should
//remove the check. [Jon Aquino]
//Or make an assertion [Jon Aquino 10/29/2003]
if (root!=NULL) return root->depth();
return 0;
}
/**
* Returns the number of items in the tree.
*/
int Quadtree::size() {
if (root!=NULL) return root->size();
return 0;
}
void
Quadtree::insert(const Envelope *itemEnv, void* item)
{
collectStats(itemEnv);
Envelope *insertEnv=ensureExtent(itemEnv,minExtent);
if ( insertEnv != itemEnv ) newEnvelopes.push_back(insertEnv);
root->insert(insertEnv,item);
#if DEBUG
cerr<<"Quadtree::insert("<<itemEnv->toString()<<", "<<item<<")"<<endl;
cerr<<" insertEnv:"<<insertEnv->toString()<<endl;
cerr<<" tree:"<<endl<<root->toString()<<endl;
#endif
}
vector<void*>*
Quadtree::query(const Envelope *searchEnv)
{
/*
* the items that are matched are the items in quads which
* overlap the search envelope
*/
vector<void*> *foundItems=new vector<void*>();
root->addAllItemsFromOverlapping(searchEnv,foundItems);
#if DEBUG
cerr<<"Quadtree::query returning "<<foundItems->size()<<" items over "<<size()<<" items in index (of depth: "<<depth()<<")"<<endl;
cerr<<" Root:\n"<<root->toString()<<endl;
#endif
return foundItems;
}
/**
* Return a list of all items in the Quadtree
*/
vector<void*>* Quadtree::queryAll() {
vector<void*> *foundItems=new vector<void*>();
root->addAllItems(foundItems);
return foundItems;
}
void Quadtree::collectStats(const Envelope *itemEnv){
double delX=itemEnv->getWidth();
if (delX<minExtent && delX>0.0)
minExtent=delX;
double delY=itemEnv->getWidth();
if (delY<minExtent && delY>0.0)
minExtent=delY;
}
string
Quadtree::toString() const
{
string ret = root->toString();
return ret;
}
} // namespace geos
/**********************************************************************
* $Log: Quadtree.cpp,v $
* Revision 1.15 2004/12/08 13:54:43 strk
* gcc warnings checked and fixed, general cleanups.
*
* Revision 1.14 2004/11/01 16:43:04 strk
* Added Profiler code.
* Temporarly patched a bug in DoubleBits (must check drawbacks).
* Various cleanups and speedups.
*
* Revision 1.13 2004/07/27 16:35:46 strk
* Geometry::getEnvelopeInternal() changed to return a const Envelope *.
* This should reduce object copies as once computed the envelope of a
* geometry remains the same.
*
* Revision 1.12 2004/07/13 08:33:52 strk
* Added missing virtual destructor to virtual classes.
* Fixed implicit unsigned int -> int casts
*
* Revision 1.11 2004/07/02 13:28:27 strk
* Fixed all #include lines to reflect headers layout change.
* Added client application build tips in README.
*
* Revision 1.10 2004/05/06 16:30:58 strk
* Kept track of newly allocated objects by ensureExtent for Bintree and Quadtree,
* deleted at destruction time. doc/example.cpp runs with no leaks.
*
* Revision 1.9 2004/04/19 15:14:45 strk
* Added missing virtual destructor in SpatialIndex class.
* Memory leaks fixes. Const and throw specifications added.
*
* Revision 1.8 2004/03/25 02:23:55 ybychkov
* All "index/" packages upgraded to JTS 1.4
*
* Revision 1.7 2003/11/07 01:23:42 pramsey
* Add standard CVS headers licence notices and copyrights to all cpp and h
* files.
*
*
**********************************************************************/
|
