File: Root.cpp

package info (click to toggle)
geos 3.4.2-6
  • links: PTS, VCS
  • area: main
  • in suites: jessie, jessie-kfreebsd
  • size: 16,572 kB
  • ctags: 13,989
  • sloc: cpp: 97,030; xml: 32,337; sh: 10,379; ansic: 3,726; php: 1,831; makefile: 1,619; ruby: 1,295; python: 928
file content (148 lines) | stat: -rw-r--r-- 3,980 bytes parent folder | download
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
/**********************************************************************
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.osgeo.org
 *
 * Copyright (C) 2006 Refractions Research Inc.
 * 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.
 *
 **********************************************************************
 *
 * Last port: index/quadtree/Root.java rev 1.7 (JTS-1.10)
 *
 **********************************************************************/

#include <geos/index/quadtree/Root.h>
#include <geos/index/quadtree/Node.h>
#include <geos/index/quadtree/IntervalSize.h>
#include <geos/geom/Coordinate.h>
#include <geos/geom/Envelope.h>

#include <cassert>
#include <cstddef>

#ifndef GEOS_DEBUG
#define GEOS_DEBUG 0
#endif

#ifdef GEOS_DEBUG
#include <iostream>
#endif

using namespace geos::geom;

namespace geos {
namespace index { // geos.index
namespace quadtree { // geos.index.quadtree

using namespace std;

// the singleton root quad is centred at the origin.
//Coordinate* Root::origin=new Coordinate(0.0, 0.0);
const Coordinate Root::origin(0.0, 0.0);

/*public*/
void
Root::insert(const Envelope *itemEnv, void* item)
{

#if GEOS_DEBUG
	std::cerr<< "Root("<<this<<")::insert("<<itemEnv->toString()<<", "<<item<<") called"<<std::endl;
#endif
	int index = getSubnodeIndex(itemEnv, origin);
	// if index is -1, itemEnv must cross the X or Y axis.
	if (index==-1)
	{
#if GEOS_DEBUG
	std::cerr<<"  -1 subnode index"<<std::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)
	 */
	Node *node = subnode[index];

#if GEOS_DEBUG
	std::cerr<<"("<<this<<") subnode["<<index<<"] @ "<<node<<std::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))
	{
		std::auto_ptr<Node> snode (node); // may be NULL
		node = 0; subnode[index] = 0;

		std::auto_ptr<Node> largerNode =
			Node::createExpanded(snode, *itemEnv);

#if GEOS_DEBUG
		std::cerr<<"("<<this<<") created expanded node " << largerNode.get() << " containing previously reported subnode" << std::endl;
#endif

		// Previous subnode was passed as a child of the larger one
		assert(!subnode[index]);
		subnode[index] = largerNode.release();
	}

#if GEOS_DEBUG
	std::cerr<<"("<<this<<") calling insertContained with subnode " << subnode[index] << std::endl;
#endif
	/*
	 * 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);

#if GEOS_DEBUG
	std::cerr<<"("<<this<<") done calling insertContained with subnode " << subnode[index] << std::endl;
#endif

	//System.out.println("depth = " + root.depth() + " size = " + root.size());
	//System.out.println(" size = " + size());
}

/*private*/
void
Root::insertContained(Node *tree, const Envelope *itemEnv, void *item)
{
	assert(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->getMinY(),
	                                         itemEnv->getMaxY());

	NodeBase *node;

	if (isZeroX || isZeroY)
	{
		node = tree->find(itemEnv);
	}
	else
	{
		node = tree->getNode(itemEnv);
	}

	node->add(item);
}

} // namespace geos.index.quadtree
} // namespace geos.index
} // namespace geos