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
|
/**********************************************************************
* $Id: QuadTreeRoot.cpp,v 1.9 2004/11/01 16:43:04 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 {
// the singleton root quad is centred at the origin.
Coordinate* QuadTreeRoot::origin=new Coordinate(0.0, 0.0);
QuadTreeRoot::QuadTreeRoot(){}
QuadTreeRoot::~QuadTreeRoot(){}
/**
* Insert an item into the quadtree this is the root of.
*/
void QuadTreeRoot::insert(const Envelope *itemEnv,void* item){
#if DEBUG
cerr<<"("<<this<<") insert("<<itemEnv->toString()<<", "<<item<<") called"<<endl;
#endif
int index=getSubnodeIndex(itemEnv,origin);
// if index is -1, itemEnv must cross the X or Y axis.
if (index==-1) {
#if DEBUG
cerr<<" -1 subnode index"<<endl;
#endif
add(item);
return;
}
/*
* the item must be contained in one quadrant, so insert it into the
* tree for that quadrant (which may not yet exist)
*/
QuadTreeNode *node=subnode[index];
#if DEBUG
cerr<<"("<<this<<") subnode["<<index<<"] @ "<<node<<endl;
#endif
/*
* If the subquad doesn't exist or this item is not contained in it,
* have to expand the tree upward to contain the item.
*/
if (node==NULL || !node->getEnvelope()->contains(itemEnv)) {
QuadTreeNode *largerNode=QuadTreeNode::createExpanded(node,itemEnv);
//delete subnode[index];
subnode[index]=largerNode;
}
/*
* At this point we have a subquad which exists and must contain
* contains the env for the item. Insert the item into the tree.
*/
insertContained(subnode[index],itemEnv,item);
//System.out.println("depth = " + root.depth() + " size = " + root.size());
//System.out.println(" size = " + size());
}
/**
* insert an item which is known to be contained in the tree rooted at
* the given QuadNode root. Lower levels of the tree will be created
* if necessary to hold the item.
*/
void
QuadTreeRoot::insertContained(QuadTreeNode *tree, const Envelope *itemEnv, void *item)
{
Assert::isTrue(tree->getEnvelope()->contains(itemEnv));
/**
* Do NOT create a new quad for zero-area envelopes - this would lead
* to infinite recursion. Instead, use a heuristic of simply returning
* the smallest existing quad containing the query
*/
bool isZeroX=IntervalSize::isZeroWidth(itemEnv->getMinX(),itemEnv->getMaxX());
bool isZeroY=IntervalSize::isZeroWidth(itemEnv->getMinX(),itemEnv->getMaxX());
QuadTreeNodeBase *node;
if (isZeroX || isZeroY)
node=tree->find(itemEnv);
else
node=tree->getNode(itemEnv);
node->add(item);
}
bool QuadTreeRoot::isSearchMatch(const Envelope *searchEnv){
return true;
}
} // namespace geos
/**********************************************************************
* $Log: QuadTreeRoot.cpp,v $
* Revision 1.9 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.8 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.7 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.6 2003/11/07 01:23:42 pramsey
* Add standard CVS headers licence notices and copyrights to all cpp and h
* files.
*
*
**********************************************************************/
|
