<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<title>GEOS: geos::index::quadtree::Quadtree Class Reference</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="doxygen.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<!-- Generated by Doxygen 1.7.1 -->
<div class="navigation" id="top">
<div class="tabs">
<ul class="tablist">
<li><a href="index.html"><span>Main Page</span></a></li>
<li><a href="pages.html"><span>Related Pages</span></a></li>
<li><a href="namespaces.html"><span>Namespaces</span></a></li>
<li class="current"><a href="annotated.html"><span>Classes</span></a></li>
<li><a href="files.html"><span>Files</span></a></li>
</ul>
</div>
<div class="tabs2">
<ul class="tablist">
<li><a href="annotated.html"><span>Class List</span></a></li>
<li><a href="hierarchy.html"><span>Class Hierarchy</span></a></li>
<li><a href="functions.html"><span>Class Members</span></a></li>
</ul>
</div>
<div class="navpath">
<ul>
<li><a class="el" href="namespacegeos.html">geos</a> </li>
<li><a class="el" href="namespacegeos_1_1index.html">index</a> </li>
<li><a class="el" href="namespacegeos_1_1index_1_1quadtree.html">quadtree</a> </li>
<li><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html">geos::index::quadtree::Quadtree</a> </li>
</ul>
</div>
</div>
<div class="header">
<div class="summary">
<a href="#pub-methods">Public Member Functions</a> |
<a href="#pub-static-methods">Static Public Member Functions</a> </div>
<div class="headertitle">
<h1>geos::index::quadtree::Quadtree Class Reference</h1> </div>
</div>
<div class="contents">
<!-- doxytag: class="geos::index::quadtree::Quadtree" --><!-- doxytag: inherits="geos::index::SpatialIndex" -->
<p>A <a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html" title="A Quadtree is a spatial index structure for efficient querying of 2D rectangles. If other kinds of sp...">Quadtree</a> 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.
<a href="#_details">More...</a></p>
<p><code>#include <<a class="el" href="Quadtree_8h_source.html">Quadtree.h</a>></code></p>
<div class="dynheader">
Inheritance diagram for geos::index::quadtree::Quadtree:</div>
<div class="dyncontent">
<div class="center">
<img src="classgeos_1_1index_1_1quadtree_1_1Quadtree.png" usemap="#geos::index::quadtree::Quadtree_map" alt=""/>
<map id="geos::index::quadtree::Quadtree_map" name="geos::index::quadtree::Quadtree_map">
<area href="classgeos_1_1index_1_1SpatialIndex.html" alt="geos::index::SpatialIndex" shape="rect" coords="0,0,189,24"/>
</map>
</div>
<p><a href="classgeos_1_1index_1_1quadtree_1_1Quadtree-members.html">List of all members.</a></p>
<table class="memberdecls">
<tr><td colspan="2"><h2><a name="pub-methods"></a>
Public Member Functions</h2></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="ad2713f35495133940ba9726fa4a742d9"></a><!-- doxytag: member="geos::index::quadtree::Quadtree::Quadtree" ref="ad2713f35495133940ba9726fa4a742d9" args="()" -->
</td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html#ad2713f35495133940ba9726fa4a742d9">Quadtree</a> ()</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Constructs a <a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html" title="A Quadtree is a spatial index structure for efficient querying of 2D rectangles. If other kinds of sp...">Quadtree</a> with zero items. <br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="a68dffc5e628225c2d04d47d9465b9da1"></a><!-- doxytag: member="geos::index::quadtree::Quadtree::depth" ref="a68dffc5e628225c2d04d47d9465b9da1" args="()" -->
int </td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html#a68dffc5e628225c2d04d47d9465b9da1">depth</a> ()</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Returns the number of levels in the tree. <br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="a3983ba7626f006dcf5eb821b44ce1500"></a><!-- doxytag: member="geos::index::quadtree::Quadtree::size" ref="a3983ba7626f006dcf5eb821b44ce1500" args="()" -->
int </td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html#a3983ba7626f006dcf5eb821b44ce1500">size</a> ()</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Returns the number of items in the tree. <br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html#a771b5ee5c0d638a145ae675e11308963">insert</a> (const <a class="el" href="classgeos_1_1geom_1_1Envelope.html">geom::Envelope</a> *itemEnv, void *item)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Adds a spatial item with an extent specified by the given Envelope to the index. <a href="#a771b5ee5c0d638a145ae675e11308963"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html#aeff52411e953a7da9bf3083004686d19">query</a> (const <a class="el" href="classgeos_1_1geom_1_1Envelope.html">geom::Envelope</a> *searchEnv, std::vector< void * > &ret)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Queries the tree and returns items which may lie in the given search envelope. <a href="#aeff52411e953a7da9bf3083004686d19"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html#a1e753c1c2c00f9d05bdf7041ce95bbb0">query</a> (const <a class="el" href="classgeos_1_1geom_1_1Envelope.html">geom::Envelope</a> *searchEnv, <a class="el" href="classgeos_1_1index_1_1ItemVisitor.html">ItemVisitor</a> &visitor)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Queries the tree and visits items which may lie in the given search envelope. <a href="#a1e753c1c2c00f9d05bdf7041ce95bbb0"></a><br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">bool </td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html#af15851c5095fbb798d86aa58c03ad341">remove</a> (const <a class="el" href="classgeos_1_1geom_1_1Envelope.html">geom::Envelope</a> *itemEnv, void *item)</td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="a00d56cce83df199ac9df9f463b81c426"></a><!-- doxytag: member="geos::index::quadtree::Quadtree::queryAll" ref="a00d56cce83df199ac9df9f463b81c426" args="()" -->
std::vector< void * > * </td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html#a00d56cce83df199ac9df9f463b81c426">queryAll</a> ()</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Return a list of all items in the <a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html" title="A Quadtree is a spatial index structure for efficient querying of 2D rectangles. If other kinds of sp...">Quadtree</a>. <br/></td></tr>
<tr><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="ac1fa605c93d39433312ddaf7a8e9e7ff"></a><!-- doxytag: member="geos::index::quadtree::Quadtree::toString" ref="ac1fa605c93d39433312ddaf7a8e9e7ff" args="() const " -->
std::string </td><td class="memItemRight" valign="bottom"><b>toString</b> () const </td></tr>
<tr><td colspan="2"><h2><a name="pub-static-methods"></a>
Static Public Member Functions</h2></td></tr>
<tr><td class="memItemLeft" align="right" valign="top">static <a class="el" href="classgeos_1_1geom_1_1Envelope.html">geom::Envelope</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html#ab8ef3d192b19bb17090b7490b5d80110">ensureExtent</a> (const <a class="el" href="classgeos_1_1geom_1_1Envelope.html">geom::Envelope</a> *itemEnv, double minExtent)</td></tr>
<tr><td class="mdescLeft"> </td><td class="mdescRight">Ensure that the envelope for the inserted item has non-zero extents. <a href="#ab8ef3d192b19bb17090b7490b5d80110"></a><br/></td></tr>
</table>
<hr/><a name="_details"></a><h2>Detailed Description</h2>
<p>A <a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html" title="A Quadtree is a spatial index structure for efficient querying of 2D rectangles. If other kinds of sp...">Quadtree</a> 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. </p>
<p>The quadtree structure is used to provide a primary filter for range rectangle queries. The <a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html#aeff52411e953a7da9bf3083004686d19" title="Queries the tree and returns items which may lie in the given search envelope.">query()</a> method returns a list of all objects which <em>may</em> 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.</p>
<p>This implementation does not require specifying the extent of the inserted items beforehand. It will automatically expand to accomodate any extent of dataset.</p>
<p>This data structure is also known as an <em>MX-CIF quadtree</em> following the usage of Samet and others. </p>
<hr/><h2>Member Function Documentation</h2>
<a class="anchor" id="ab8ef3d192b19bb17090b7490b5d80110"></a><!-- doxytag: member="geos::index::quadtree::Quadtree::ensureExtent" ref="ab8ef3d192b19bb17090b7490b5d80110" args="(const geom::Envelope *itemEnv, double minExtent)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">static <a class="el" href="classgeos_1_1geom_1_1Envelope.html">geom::Envelope</a>* geos::index::quadtree::Quadtree::ensureExtent </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="classgeos_1_1geom_1_1Envelope.html">geom::Envelope</a> * </td>
<td class="paramname"> <em>itemEnv</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">double </td>
<td class="paramname"> <em>minExtent</em></td><td> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td><td><code> [static]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Ensure that the envelope for the inserted item has non-zero extents. </p>
<p>Use the current minExtent to pad the envelope, if necessary. Can return a new Envelope or the given one (casted to non-const). </p>
</div>
</div>
<a class="anchor" id="a771b5ee5c0d638a145ae675e11308963"></a><!-- doxytag: member="geos::index::quadtree::Quadtree::insert" ref="a771b5ee5c0d638a145ae675e11308963" args="(const geom::Envelope *itemEnv, void *item)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">void geos::index::quadtree::Quadtree::insert </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="classgeos_1_1geom_1_1Envelope.html">geom::Envelope</a> * </td>
<td class="paramname"> <em>itemEnv</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">void * </td>
<td class="paramname"> <em>item</em></td><td> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td><td><code> [virtual]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Adds a spatial item with an extent specified by the given Envelope to the index. </p>
<dl><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>itemEnv</em> </td><td>Envelope of the item, ownership left to caller. TODO: Reference hold by this class ?</td></tr>
<tr><td valign="top"></td><td valign="top"><em>item</em> </td><td>Opaque item, ownership left to caller. Reference hold by this class. </td></tr>
</table>
</dd>
</dl>
<p>Implements <a class="el" href="classgeos_1_1index_1_1SpatialIndex.html#aaac40880b4fbc4a32d1d0aba1d679117">geos::index::SpatialIndex</a>.</p>
</div>
</div>
<a class="anchor" id="aeff52411e953a7da9bf3083004686d19"></a><!-- doxytag: member="geos::index::quadtree::Quadtree::query" ref="aeff52411e953a7da9bf3083004686d19" args="(const geom::Envelope *searchEnv, std::vector< void * > &ret)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">void geos::index::quadtree::Quadtree::query </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="classgeos_1_1geom_1_1Envelope.html">geom::Envelope</a> * </td>
<td class="paramname"> <em>searchEnv</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">std::vector< void * > & </td>
<td class="paramname"> <em>ret</em></td><td> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td><td><code> [virtual]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Queries the tree and returns items which may lie in the given search envelope. </p>
<p>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.</p>
<dl><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>searchEnv</em> </td><td>the envelope of the desired query area. </td></tr>
<tr><td valign="top"></td><td valign="top"><em>ret</em> </td><td>a vector where items which may intersect the search envelope are pushed </td></tr>
</table>
</dd>
</dl>
<p>Implements <a class="el" href="classgeos_1_1index_1_1SpatialIndex.html#aec3aa2aafa2eff5679c75388afb34ab2">geos::index::SpatialIndex</a>.</p>
</div>
</div>
<a class="anchor" id="a1e753c1c2c00f9d05bdf7041ce95bbb0"></a><!-- doxytag: member="geos::index::quadtree::Quadtree::query" ref="a1e753c1c2c00f9d05bdf7041ce95bbb0" args="(const geom::Envelope *searchEnv, ItemVisitor &visitor)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">void geos::index::quadtree::Quadtree::query </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="classgeos_1_1geom_1_1Envelope.html">geom::Envelope</a> * </td>
<td class="paramname"> <em>searchEnv</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype"><a class="el" href="classgeos_1_1index_1_1ItemVisitor.html">ItemVisitor</a> & </td>
<td class="paramname"> <em>visitor</em></td><td> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td><td><code> [inline, virtual]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Queries the tree and visits items which may lie in the given search envelope. </p>
<p>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.</p>
<dl><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>searchEnv</em> </td><td>the envelope of the desired query area. </td></tr>
<tr><td valign="top"></td><td valign="top"><em>visitor</em> </td><td>a visitor object which is passed the visited items </td></tr>
</table>
</dd>
</dl>
<p>Implements <a class="el" href="classgeos_1_1index_1_1SpatialIndex.html#ab79a4e1da4835cbfa030f25867effcde">geos::index::SpatialIndex</a>.</p>
</div>
</div>
<a class="anchor" id="af15851c5095fbb798d86aa58c03ad341"></a><!-- doxytag: member="geos::index::quadtree::Quadtree::remove" ref="af15851c5095fbb798d86aa58c03ad341" args="(const geom::Envelope *itemEnv, void *item)" -->
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">bool geos::index::quadtree::Quadtree::remove </td>
<td>(</td>
<td class="paramtype">const <a class="el" href="classgeos_1_1geom_1_1Envelope.html">geom::Envelope</a> * </td>
<td class="paramname"> <em>itemEnv</em>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">void * </td>
<td class="paramname"> <em>item</em></td><td> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td><td><code> [virtual]</code></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Removes a single item from the tree.</p>
<dl><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>itemEnv</em> </td><td>the Envelope of the item to be removed </td></tr>
<tr><td valign="top"></td><td valign="top"><em>item</em> </td><td>the item to remove </td></tr>
</table>
</dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd><code>true</code> if the item was found (and thus removed) </dd></dl>
<p>Implements <a class="el" href="classgeos_1_1index_1_1SpatialIndex.html#a70adf500577ec4c6a595d3d26196eb04">geos::index::SpatialIndex</a>.</p>
</div>
</div>
<hr/>The documentation for this class was generated from the following file:<ul>
<li><a class="el" href="Quadtree_8h_source.html">Quadtree.h</a></li>
</ul>
</div>
<hr class="footer"/><address class="footer"><small>Generated on Thu Jul 22 2010 for GEOS by
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.7.1 </small></address>
</body>
</html>
