/usr/include/geos/index/quadtree/Quadtree.h is in libgeos-dev 3.2.2-3ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 186 187 188 189 190 191 192 193 194 195 196 197 198 | /**********************************************************************
* $Id: Quadtree.h 2556 2009-06-06 22:22:28Z strk $
*
* GEOS - Geometry Engine Open Source
* http://geos.refractions.net
*
* Copyright (C) 2006 Refractions Research 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/Quadtree.java rev. 1.16 (JTS-1.10)
*
**********************************************************************/
#ifndef GEOS_IDX_QUADTREE_QUADTREE_H
#define GEOS_IDX_QUADTREE_QUADTREE_H
#include <geos/export.h>
#include <geos/index/SpatialIndex.h> // for inheritance
#include <geos/index/quadtree/Root.h> // for composition
#include <vector>
#include <string>
// Forward declarations
namespace geos {
namespace geom {
class Envelope;
}
namespace index {
namespace quadtree {
// class Root;
}
}
}
namespace geos {
namespace index { // geos::index
namespace quadtree { // geos::index::quadtree
/**
* \brief
* A Quadtree is a spatial index structure for efficient querying
* of 2D rectangles. If other kinds of spatial objects
* need to be indexed they can be represented by their
* envelopes
*
* The quadtree structure is used to provide a primary filter
* for range rectangle queries. The query() method returns a list of
* all objects which <i>may</i> intersect the query rectangle. Note that
* it may return objects which do not in fact intersect.
* A secondary filter is required to test for exact intersection.
* Of course, this secondary filter may consist of other tests besides
* intersection, such as testing other kinds of spatial relationships.
*
* This implementation does not require specifying the extent of the inserted
* items beforehand. It will automatically expand to accomodate any extent
* of dataset.
*
* This data structure is also known as an <i>MX-CIF quadtree</i>
* following the usage of Samet and others.
*/
class GEOS_DLL Quadtree: public SpatialIndex {
private:
std::vector<geom::Envelope *> newEnvelopes;
void collectStats(const geom::Envelope& itemEnv);
Root root;
/**
* Statistics
*
* minExtent is the minimum envelope extent of all items
* inserted into the tree so far. It is used as a heuristic value
* to construct non-zero envelopes for features with zero X and/or
* Y extent.
* Start with a non-zero extent, in case the first feature inserted has
* a zero extent in both directions. This value may be non-optimal, but
* only one feature will be inserted with this value.
*/
double minExtent;
public:
/**
* \brief
* 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 (casted to non-const).
*/
static geom::Envelope* ensureExtent(const geom::Envelope *itemEnv,
double minExtent);
/**
* \brief
* Constructs a Quadtree with zero items.
*/
Quadtree()
:
root(),
minExtent(1.0)
{}
~Quadtree();
/// Returns the number of levels in the tree.
int depth();
/// Returns the number of items in the tree.
int size();
void insert(const geom::Envelope *itemEnv, void *item);
/** \brief
* Queries the tree and returns items which may lie
* in the given search envelope.
*
* Precisely, the items that are returned are all items in the tree
* whose envelope <b>may</b> intersect the search Envelope.
* Note that some items with non-intersecting envelopes may be
* returned as well;
* the client is responsible for filtering these out.
* In most situations there will be many items in the tree which do not
* intersect the search envelope and which are not returned - thus
* providing improved performance over a simple linear scan.
*
* @param searchEnv the envelope of the desired query area.
* @param ret a vector where items which may intersect the
* search envelope are pushed
*/
void query(const geom::Envelope *searchEnv, std::vector<void*>& ret);
/** \brief
* Queries the tree and visits items which may lie in
* the given search envelope.
*
* Precisely, the items that are visited are all items in the tree
* whose envelope <b>may</b> intersect the search Envelope.
* Note that some items with non-intersecting envelopes may be
* visited as well;
* the client is responsible for filtering these out.
* In most situations there will be many items in the tree which do not
* intersect the search envelope and which are not visited - thus
* providing improved performance over a simple linear scan.
*
* @param searchEnv the envelope of the desired query area.
* @param visitor a visitor object which is passed the visited items
*/
void query(const geom::Envelope *searchEnv, ItemVisitor& visitor)
{
/*
* the items that are matched are the items in quads which
* overlap the search envelope
*/
root.visit(searchEnv, visitor);
}
/**
* Removes a single item from the tree.
*
* @param itemEnv the Envelope of the item to be removed
* @param item the item to remove
* @return <code>true</code> if the item was found (and thus removed)
*/
bool remove(const geom::Envelope* itemEnv, void* item);
/// Return a list of all items in the Quadtree
std::vector<void*>* queryAll();
std::string toString() const;
};
} // namespace geos::index::quadtree
} // namespace geos::index
} // namespace geos
#endif // GEOS_IDX_QUADTREE_QUADTREE_H
/**********************************************************************
* $Log$
* Revision 1.2 2006/04/03 08:29:30 strk
* Added port info, cleaned up log message, minor assertion checking.
*
* Revision 1.1 2006/03/22 12:22:50 strk
* indexQuadtree.h split
*
**********************************************************************/
|