647 lines
36 KiB
HTML
647 lines
36 KiB
HTML
|
<!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"/>
|
||
|
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
|
||
|
<meta name="generator" content="Doxygen 1.8.11"/>
|
||
|
<title>GEOS: geos::index::quadtree::Quadtree Class Reference</title>
|
||
|
<link href="tabs.css" rel="stylesheet" type="text/css"/>
|
||
|
<script type="text/javascript" src="jquery.js"></script>
|
||
|
<script type="text/javascript" src="dynsections.js"></script>
|
||
|
<link href="doxygen.css" rel="stylesheet" type="text/css" />
|
||
|
</head>
|
||
|
<body>
|
||
|
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
|
||
|
<div id="titlearea">
|
||
|
<table cellspacing="0" cellpadding="0">
|
||
|
<tbody>
|
||
|
<tr style="height: 56px;">
|
||
|
<td id="projectalign" style="padding-left: 0.5em;">
|
||
|
<div id="projectname">GEOS
|
||
|
 <span id="projectnumber">3.9.1dev</span>
|
||
|
</div>
|
||
|
</td>
|
||
|
</tr>
|
||
|
</tbody>
|
||
|
</table>
|
||
|
</div>
|
||
|
<!-- end header part -->
|
||
|
<!-- Generated by Doxygen 1.8.11 -->
|
||
|
<div id="navrow1" 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 id="navrow2" class="tabs2">
|
||
|
<ul class="tablist">
|
||
|
<li><a href="annotated.html"><span>Class List</span></a></li>
|
||
|
<li><a href="inherits.html"><span>Class Hierarchy</span></a></li>
|
||
|
<li><a href="functions.html"><span>Class Members</span></a></li>
|
||
|
</ul>
|
||
|
</div>
|
||
|
<div id="nav-path" class="navpath">
|
||
|
<ul>
|
||
|
<li class="navelem"><a class="el" href="namespacegeos.html">geos</a></li><li class="navelem"><a class="el" href="namespacegeos_1_1index.html">index</a></li><li class="navelem"><a class="el" href="namespacegeos_1_1index_1_1quadtree.html">quadtree</a></li><li class="navelem"><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html">Quadtree</a></li> </ul>
|
||
|
</div>
|
||
|
</div><!-- top -->
|
||
|
<div class="header">
|
||
|
<div class="summary">
|
||
|
<a href="#pub-methods">Public Member Functions</a> |
|
||
|
<a href="#pub-static-methods">Static Public Member Functions</a> |
|
||
|
<a href="#pri-methods">Private Member Functions</a> |
|
||
|
<a href="#pri-attribs">Private Attributes</a> |
|
||
|
<a href="classgeos_1_1index_1_1quadtree_1_1Quadtree-members.html">List of all members</a> </div>
|
||
|
<div class="headertitle">
|
||
|
<div class="title">geos::index::quadtree::Quadtree Class Reference</div> </div>
|
||
|
</div><!--header-->
|
||
|
<div class="contents">
|
||
|
|
||
|
<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="classgeos_1_1index_1_1quadtree_1_1Quadtree.html#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"><iframe scrolling="no" frameborder="0" src="classgeos_1_1index_1_1quadtree_1_1Quadtree__inherit__graph.svg" width="194" height="131"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe>
|
||
|
</div>
|
||
|
<center><span class="legend">[<a href="graph_legend.html">legend</a>]</span></center></div>
|
||
|
<div class="dynheader">
|
||
|
Collaboration diagram for geos::index::quadtree::Quadtree:</div>
|
||
|
<div class="dyncontent">
|
||
|
<div class="center"><iframe scrolling="no" frameborder="0" src="classgeos_1_1index_1_1quadtree_1_1Quadtree__coll__graph.svg" width="619" height="271"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe>
|
||
|
</div>
|
||
|
<center><span class="legend">[<a href="graph_legend.html">legend</a>]</span></center></div>
|
||
|
<table class="memberdecls">
|
||
|
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="pub-methods"></a>
|
||
|
Public Member Functions</h2></td></tr>
|
||
|
<tr class="memitem:ad2713f35495133940ba9726fa4a742d9"><td class="memItemLeft" align="right" valign="top"> </td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html#ad2713f35495133940ba9726fa4a742d9">Quadtree</a> ()</td></tr>
|
||
|
<tr class="memdesc:ad2713f35495133940ba9726fa4a742d9"><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. <a href="#ad2713f35495133940ba9726fa4a742d9">More...</a><br /></td></tr>
|
||
|
<tr class="separator:ad2713f35495133940ba9726fa4a742d9"><td class="memSeparator" colspan="2"> </td></tr>
|
||
|
<tr class="memitem:aa86b908c877102b62fd6a41d28cc5904"><td class="memItemLeft" align="right" valign="top"> </td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html#aa86b908c877102b62fd6a41d28cc5904">~Quadtree</a> () override=default</td></tr>
|
||
|
<tr class="separator:aa86b908c877102b62fd6a41d28cc5904"><td class="memSeparator" colspan="2"> </td></tr>
|
||
|
<tr class="memitem:a68dffc5e628225c2d04d47d9465b9da1"><td class="memItemLeft" align="right" valign="top">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 class="memdesc:a68dffc5e628225c2d04d47d9465b9da1"><td class="mdescLeft"> </td><td class="mdescRight">Returns the number of levels in the tree. <a href="#a68dffc5e628225c2d04d47d9465b9da1">More...</a><br /></td></tr>
|
||
|
<tr class="separator:a68dffc5e628225c2d04d47d9465b9da1"><td class="memSeparator" colspan="2"> </td></tr>
|
||
|
<tr class="memitem:aa02a6f7635c1e1ae6ab19e548c557d0c"><td class="memItemLeft" align="right" valign="top">size_t </td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html#aa02a6f7635c1e1ae6ab19e548c557d0c">size</a> ()</td></tr>
|
||
|
<tr class="memdesc:aa02a6f7635c1e1ae6ab19e548c557d0c"><td class="mdescLeft"> </td><td class="mdescRight">Returns the number of items in the tree. <a href="#aa02a6f7635c1e1ae6ab19e548c557d0c">More...</a><br /></td></tr>
|
||
|
<tr class="separator:aa02a6f7635c1e1ae6ab19e548c557d0c"><td class="memSeparator" colspan="2"> </td></tr>
|
||
|
<tr class="memitem:ace675add240510cea1486eb5daf0c062"><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#ace675add240510cea1486eb5daf0c062">insert</a> (const <a class="el" href="classgeos_1_1geom_1_1Envelope.html">geom::Envelope</a> *itemEnv, void *item) override</td></tr>
|
||
|
<tr class="memdesc:ace675add240510cea1486eb5daf0c062"><td class="mdescLeft"> </td><td class="mdescRight">Adds a spatial item with an extent specified by the given Envelope to the index. <a href="#ace675add240510cea1486eb5daf0c062">More...</a><br /></td></tr>
|
||
|
<tr class="separator:ace675add240510cea1486eb5daf0c062"><td class="memSeparator" colspan="2"> </td></tr>
|
||
|
<tr class="memitem:ad8c1eb5215ad191bfbd38e8936677e72"><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#ad8c1eb5215ad191bfbd38e8936677e72">query</a> (const <a class="el" href="classgeos_1_1geom_1_1Envelope.html">geom::Envelope</a> *searchEnv, std::vector< void * > &ret) override</td></tr>
|
||
|
<tr class="memdesc:ad8c1eb5215ad191bfbd38e8936677e72"><td class="mdescLeft"> </td><td class="mdescRight">Queries the tree and returns items which may lie in the given search envelope. <a href="#ad8c1eb5215ad191bfbd38e8936677e72">More...</a><br /></td></tr>
|
||
|
<tr class="separator:ad8c1eb5215ad191bfbd38e8936677e72"><td class="memSeparator" colspan="2"> </td></tr>
|
||
|
<tr class="memitem:a4f688e0830d53e6ec3ba397f606e9008"><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#a4f688e0830d53e6ec3ba397f606e9008">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) override</td></tr>
|
||
|
<tr class="memdesc:a4f688e0830d53e6ec3ba397f606e9008"><td class="mdescLeft"> </td><td class="mdescRight">Queries the tree and visits items which may lie in the given search envelope. <a href="#a4f688e0830d53e6ec3ba397f606e9008">More...</a><br /></td></tr>
|
||
|
<tr class="separator:a4f688e0830d53e6ec3ba397f606e9008"><td class="memSeparator" colspan="2"> </td></tr>
|
||
|
<tr class="memitem:a30af72119aa17b1a34442e9291aa7b4b"><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#a30af72119aa17b1a34442e9291aa7b4b">remove</a> (const <a class="el" href="classgeos_1_1geom_1_1Envelope.html">geom::Envelope</a> *itemEnv, void *item) override</td></tr>
|
||
|
<tr class="separator:a30af72119aa17b1a34442e9291aa7b4b"><td class="memSeparator" colspan="2"> </td></tr>
|
||
|
<tr class="memitem:a00d56cce83df199ac9df9f463b81c426"><td class="memItemLeft" align="right" valign="top">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 class="memdesc:a00d56cce83df199ac9df9f463b81c426"><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>. <a href="#a00d56cce83df199ac9df9f463b81c426">More...</a><br /></td></tr>
|
||
|
<tr class="separator:a00d56cce83df199ac9df9f463b81c426"><td class="memSeparator" colspan="2"> </td></tr>
|
||
|
<tr class="memitem:ac1fa605c93d39433312ddaf7a8e9e7ff"><td class="memItemLeft" align="right" valign="top">std::string </td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html#ac1fa605c93d39433312ddaf7a8e9e7ff">toString</a> () const </td></tr>
|
||
|
<tr class="separator:ac1fa605c93d39433312ddaf7a8e9e7ff"><td class="memSeparator" colspan="2"> </td></tr>
|
||
|
<tr class="memitem:a21f17aacc36cc529713efc0c17485598"><td class="memItemLeft" align="right" valign="top"> </td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html#a21f17aacc36cc529713efc0c17485598">Quadtree</a> (const <a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html">Quadtree</a> &)=delete</td></tr>
|
||
|
<tr class="separator:a21f17aacc36cc529713efc0c17485598"><td class="memSeparator" colspan="2"> </td></tr>
|
||
|
<tr class="memitem:a3a00036c64db0c11bfc0781361f23b16"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html">Quadtree</a> & </td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html#a3a00036c64db0c11bfc0781361f23b16">operator=</a> (const <a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html">Quadtree</a> &)=delete</td></tr>
|
||
|
<tr class="separator:a3a00036c64db0c11bfc0781361f23b16"><td class="memSeparator" colspan="2"> </td></tr>
|
||
|
<tr class="inherit_header pub_methods_classgeos_1_1index_1_1SpatialIndex"><td colspan="2" onclick="javascript:toggleInherit('pub_methods_classgeos_1_1index_1_1SpatialIndex')"><img src="closed.png" alt="-"/> Public Member Functions inherited from <a class="el" href="classgeos_1_1index_1_1SpatialIndex.html">geos::index::SpatialIndex</a></td></tr>
|
||
|
<tr class="memitem:a877d6b8da4c0b28041aeb94297e7021c inherit pub_methods_classgeos_1_1index_1_1SpatialIndex"><td class="memItemLeft" align="right" valign="top">virtual </td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1index_1_1SpatialIndex.html#a877d6b8da4c0b28041aeb94297e7021c">~SpatialIndex</a> ()</td></tr>
|
||
|
<tr class="separator:a877d6b8da4c0b28041aeb94297e7021c inherit pub_methods_classgeos_1_1index_1_1SpatialIndex"><td class="memSeparator" colspan="2"> </td></tr>
|
||
|
</table><table class="memberdecls">
|
||
|
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="pub-static-methods"></a>
|
||
|
Static Public Member Functions</h2></td></tr>
|
||
|
<tr class="memitem:ab8ef3d192b19bb17090b7490b5d80110"><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 <a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html#a1bf75998e2b71ee8350ad292f23758ff">minExtent</a>)</td></tr>
|
||
|
<tr class="memdesc:ab8ef3d192b19bb17090b7490b5d80110"><td class="mdescLeft"> </td><td class="mdescRight">Ensure that the envelope for the inserted item has non-zero extents. <a href="#ab8ef3d192b19bb17090b7490b5d80110">More...</a><br /></td></tr>
|
||
|
<tr class="separator:ab8ef3d192b19bb17090b7490b5d80110"><td class="memSeparator" colspan="2"> </td></tr>
|
||
|
</table><table class="memberdecls">
|
||
|
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="pri-methods"></a>
|
||
|
Private Member Functions</h2></td></tr>
|
||
|
<tr class="memitem:a4ece935d8f88183a1c4c66d2daf6b7f4"><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#a4ece935d8f88183a1c4c66d2daf6b7f4">collectStats</a> (const <a class="el" href="classgeos_1_1geom_1_1Envelope.html">geom::Envelope</a> &itemEnv)</td></tr>
|
||
|
<tr class="separator:a4ece935d8f88183a1c4c66d2daf6b7f4"><td class="memSeparator" colspan="2"> </td></tr>
|
||
|
</table><table class="memberdecls">
|
||
|
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="pri-attribs"></a>
|
||
|
Private Attributes</h2></td></tr>
|
||
|
<tr class="memitem:aef9905e39e63473c525ab6970b9a6d6f"><td class="memItemLeft" align="right" valign="top">std::vector< std::unique_ptr< <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#aef9905e39e63473c525ab6970b9a6d6f">newEnvelopes</a></td></tr>
|
||
|
<tr class="separator:aef9905e39e63473c525ab6970b9a6d6f"><td class="memSeparator" colspan="2"> </td></tr>
|
||
|
<tr class="memitem:ac0082e2d5d3525f90c61e25bb6093489"><td class="memItemLeft" align="right" valign="top"><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Root.html">Root</a> </td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html#ac0082e2d5d3525f90c61e25bb6093489">root</a></td></tr>
|
||
|
<tr class="separator:ac0082e2d5d3525f90c61e25bb6093489"><td class="memSeparator" colspan="2"> </td></tr>
|
||
|
<tr class="memitem:a1bf75998e2b71ee8350ad292f23758ff"><td class="memItemLeft" align="right" valign="top">double </td><td class="memItemRight" valign="bottom"><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html#a1bf75998e2b71ee8350ad292f23758ff">minExtent</a></td></tr>
|
||
|
<tr class="separator:a1bf75998e2b71ee8350ad292f23758ff"><td class="memSeparator" colspan="2"> </td></tr>
|
||
|
</table>
|
||
|
<a name="details" id="details"></a><h2 class="groupheader">Detailed Description</h2>
|
||
|
<div class="textblock"><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#ad8c1eb5215ad191bfbd38e8936677e72" 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>
|
||
|
|
||
|
<p>Definition at line <a class="el" href="Quadtree_8h_source.html#l00071">71</a> of file <a class="el" href="Quadtree_8h_source.html">Quadtree.h</a>.</p>
|
||
|
</div><h2 class="groupheader">Constructor & Destructor Documentation</h2>
|
||
|
<a class="anchor" id="ad2713f35495133940ba9726fa4a742d9"></a>
|
||
|
<div class="memitem">
|
||
|
<div class="memproto">
|
||
|
<table class="mlabels">
|
||
|
<tr>
|
||
|
<td class="mlabels-left">
|
||
|
<table class="memname">
|
||
|
<tr>
|
||
|
<td class="memname">geos::index::quadtree::Quadtree::Quadtree </td>
|
||
|
<td>(</td>
|
||
|
<td class="paramname"></td><td>)</td>
|
||
|
<td></td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</td>
|
||
|
<td class="mlabels-right">
|
||
|
<span class="mlabels"><span class="mlabel">inline</span></span> </td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</div><div class="memdoc">
|
||
|
|
||
|
<p>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. </p>
|
||
|
|
||
|
<p>Definition at line <a class="el" href="Quadtree_8h_source.html#l00109">109</a> of file <a class="el" href="Quadtree_8h_source.html">Quadtree.h</a>.</p>
|
||
|
|
||
|
</div>
|
||
|
</div>
|
||
|
<a class="anchor" id="aa86b908c877102b62fd6a41d28cc5904"></a>
|
||
|
<div class="memitem">
|
||
|
<div class="memproto">
|
||
|
<table class="mlabels">
|
||
|
<tr>
|
||
|
<td class="mlabels-left">
|
||
|
<table class="memname">
|
||
|
<tr>
|
||
|
<td class="memname">geos::index::quadtree::Quadtree::~Quadtree </td>
|
||
|
<td>(</td>
|
||
|
<td class="paramname"></td><td>)</td>
|
||
|
<td></td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</td>
|
||
|
<td class="mlabels-right">
|
||
|
<span class="mlabels"><span class="mlabel">override</span><span class="mlabel">default</span></span> </td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</div><div class="memdoc">
|
||
|
|
||
|
</div>
|
||
|
</div>
|
||
|
<a class="anchor" id="a21f17aacc36cc529713efc0c17485598"></a>
|
||
|
<div class="memitem">
|
||
|
<div class="memproto">
|
||
|
<table class="mlabels">
|
||
|
<tr>
|
||
|
<td class="mlabels-left">
|
||
|
<table class="memname">
|
||
|
<tr>
|
||
|
<td class="memname">geos::index::quadtree::Quadtree::Quadtree </td>
|
||
|
<td>(</td>
|
||
|
<td class="paramtype">const <a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html">Quadtree</a> & </td>
|
||
|
<td class="paramname"></td><td>)</td>
|
||
|
<td></td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</td>
|
||
|
<td class="mlabels-right">
|
||
|
<span class="mlabels"><span class="mlabel">delete</span></span> </td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</div><div class="memdoc">
|
||
|
<p>Disable copy construction and assignment. Apparently needed to make this class compile under MSVC. (See <a href="https://stackoverflow.com/q/29565299">https://stackoverflow.com/q/29565299</a>) </p>
|
||
|
|
||
|
</div>
|
||
|
</div>
|
||
|
<h2 class="groupheader">Member Function Documentation</h2>
|
||
|
<a class="anchor" id="a4ece935d8f88183a1c4c66d2daf6b7f4"></a>
|
||
|
<div class="memitem">
|
||
|
<div class="memproto">
|
||
|
<table class="mlabels">
|
||
|
<tr>
|
||
|
<td class="mlabels-left">
|
||
|
<table class="memname">
|
||
|
<tr>
|
||
|
<td class="memname">void geos::index::quadtree::Quadtree::collectStats </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><td>)</td>
|
||
|
<td></td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</td>
|
||
|
<td class="mlabels-right">
|
||
|
<span class="mlabels"><span class="mlabel">private</span></span> </td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</div><div class="memdoc">
|
||
|
|
||
|
</div>
|
||
|
</div>
|
||
|
<a class="anchor" id="a68dffc5e628225c2d04d47d9465b9da1"></a>
|
||
|
<div class="memitem">
|
||
|
<div class="memproto">
|
||
|
<table class="memname">
|
||
|
<tr>
|
||
|
<td class="memname">int geos::index::quadtree::Quadtree::depth </td>
|
||
|
<td>(</td>
|
||
|
<td class="paramname"></td><td>)</td>
|
||
|
<td></td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</div><div class="memdoc">
|
||
|
|
||
|
<p>Returns the number of levels in the tree. </p>
|
||
|
|
||
|
</div>
|
||
|
</div>
|
||
|
<a class="anchor" id="ab8ef3d192b19bb17090b7490b5d80110"></a>
|
||
|
<div class="memitem">
|
||
|
<div class="memproto">
|
||
|
<table class="mlabels">
|
||
|
<tr>
|
||
|
<td class="mlabels-left">
|
||
|
<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>
|
||
|
</tr>
|
||
|
<tr>
|
||
|
<td></td>
|
||
|
<td>)</td>
|
||
|
<td></td><td></td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</td>
|
||
|
<td class="mlabels-right">
|
||
|
<span class="mlabels"><span class="mlabel">static</span></span> </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="ace675add240510cea1486eb5daf0c062"></a>
|
||
|
<div class="memitem">
|
||
|
<div class="memproto">
|
||
|
<table class="mlabels">
|
||
|
<tr>
|
||
|
<td class="mlabels-left">
|
||
|
<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>
|
||
|
</tr>
|
||
|
<tr>
|
||
|
<td></td>
|
||
|
<td>)</td>
|
||
|
<td></td><td></td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</td>
|
||
|
<td class="mlabels-right">
|
||
|
<span class="mlabels"><span class="mlabel">override</span><span class="mlabel">virtual</span></span> </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 class="params"><dt>Parameters</dt><dd>
|
||
|
<table class="params">
|
||
|
<tr><td class="paramname">itemEnv</td><td>Envelope of the item, ownership left to caller. TODO: Reference hold by this class ?</td></tr>
|
||
|
<tr><td class="paramname">item</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="a3a00036c64db0c11bfc0781361f23b16"></a>
|
||
|
<div class="memitem">
|
||
|
<div class="memproto">
|
||
|
<table class="mlabels">
|
||
|
<tr>
|
||
|
<td class="mlabels-left">
|
||
|
<table class="memname">
|
||
|
<tr>
|
||
|
<td class="memname"><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html">Quadtree</a>& geos::index::quadtree::Quadtree::operator= </td>
|
||
|
<td>(</td>
|
||
|
<td class="paramtype">const <a class="el" href="classgeos_1_1index_1_1quadtree_1_1Quadtree.html">Quadtree</a> & </td>
|
||
|
<td class="paramname"></td><td>)</td>
|
||
|
<td></td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</td>
|
||
|
<td class="mlabels-right">
|
||
|
<span class="mlabels"><span class="mlabel">delete</span></span> </td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</div><div class="memdoc">
|
||
|
|
||
|
</div>
|
||
|
</div>
|
||
|
<a class="anchor" id="ad8c1eb5215ad191bfbd38e8936677e72"></a>
|
||
|
<div class="memitem">
|
||
|
<div class="memproto">
|
||
|
<table class="mlabels">
|
||
|
<tr>
|
||
|
<td class="mlabels-left">
|
||
|
<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>
|
||
|
</tr>
|
||
|
<tr>
|
||
|
<td></td>
|
||
|
<td>)</td>
|
||
|
<td></td><td></td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</td>
|
||
|
<td class="mlabels-right">
|
||
|
<span class="mlabels"><span class="mlabel">override</span><span class="mlabel">virtual</span></span> </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 class="params"><dt>Parameters</dt><dd>
|
||
|
<table class="params">
|
||
|
<tr><td class="paramname">searchEnv</td><td>the envelope of the desired query area. </td></tr>
|
||
|
<tr><td class="paramname">ret</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="a4f688e0830d53e6ec3ba397f606e9008"></a>
|
||
|
<div class="memitem">
|
||
|
<div class="memproto">
|
||
|
<table class="mlabels">
|
||
|
<tr>
|
||
|
<td class="mlabels-left">
|
||
|
<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>
|
||
|
</tr>
|
||
|
<tr>
|
||
|
<td></td>
|
||
|
<td>)</td>
|
||
|
<td></td><td></td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</td>
|
||
|
<td class="mlabels-right">
|
||
|
<span class="mlabels"><span class="mlabel">inline</span><span class="mlabel">override</span><span class="mlabel">virtual</span></span> </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 class="params"><dt>Parameters</dt><dd>
|
||
|
<table class="params">
|
||
|
<tr><td class="paramname">searchEnv</td><td>the envelope of the desired query area. </td></tr>
|
||
|
<tr><td class="paramname">visitor</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>
|
||
|
|
||
|
<p>Definition at line <a class="el" href="Quadtree_8h_source.html#l00162">162</a> of file <a class="el" href="Quadtree_8h_source.html">Quadtree.h</a>.</p>
|
||
|
|
||
|
<p>References <a class="el" href="classgeos_1_1index_1_1quadtree_1_1NodeBase.html#a9911c1f0490448ddb228c6d7ba09dc4f">geos::index::quadtree::NodeBase::visit()</a>.</p>
|
||
|
|
||
|
<p><div class="dynheader">
|
||
|
Here is the call graph for this function:</div>
|
||
|
<div class="dyncontent">
|
||
|
<div class="center"><iframe scrolling="no" frameborder="0" src="classgeos_1_1index_1_1quadtree_1_1Quadtree_a4f688e0830d53e6ec3ba397f606e9008_cgraph.svg" width="379" height="55"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe>
|
||
|
</div>
|
||
|
</div>
|
||
|
</p>
|
||
|
|
||
|
</div>
|
||
|
</div>
|
||
|
<a class="anchor" id="a00d56cce83df199ac9df9f463b81c426"></a>
|
||
|
<div class="memitem">
|
||
|
<div class="memproto">
|
||
|
<table class="memname">
|
||
|
<tr>
|
||
|
<td class="memname">std::vector<void*>* geos::index::quadtree::Quadtree::queryAll </td>
|
||
|
<td>(</td>
|
||
|
<td class="paramname"></td><td>)</td>
|
||
|
<td></td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</div><div class="memdoc">
|
||
|
|
||
|
<p>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>. </p>
|
||
|
|
||
|
</div>
|
||
|
</div>
|
||
|
<a class="anchor" id="a30af72119aa17b1a34442e9291aa7b4b"></a>
|
||
|
<div class="memitem">
|
||
|
<div class="memproto">
|
||
|
<table class="mlabels">
|
||
|
<tr>
|
||
|
<td class="mlabels-left">
|
||
|
<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>
|
||
|
</tr>
|
||
|
<tr>
|
||
|
<td></td>
|
||
|
<td>)</td>
|
||
|
<td></td><td></td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</td>
|
||
|
<td class="mlabels-right">
|
||
|
<span class="mlabels"><span class="mlabel">override</span><span class="mlabel">virtual</span></span> </td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</div><div class="memdoc">
|
||
|
<p>Removes a single item from the tree.</p>
|
||
|
<dl class="params"><dt>Parameters</dt><dd>
|
||
|
<table class="params">
|
||
|
<tr><td class="paramname">itemEnv</td><td>the Envelope of the item to be removed </td></tr>
|
||
|
<tr><td class="paramname">item</td><td>the item to remove </td></tr>
|
||
|
</table>
|
||
|
</dd>
|
||
|
</dl>
|
||
|
<dl class="section return"><dt>Returns</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>
|
||
|
<a class="anchor" id="aa02a6f7635c1e1ae6ab19e548c557d0c"></a>
|
||
|
<div class="memitem">
|
||
|
<div class="memproto">
|
||
|
<table class="memname">
|
||
|
<tr>
|
||
|
<td class="memname">size_t geos::index::quadtree::Quadtree::size </td>
|
||
|
<td>(</td>
|
||
|
<td class="paramname"></td><td>)</td>
|
||
|
<td></td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</div><div class="memdoc">
|
||
|
|
||
|
<p>Returns the number of items in the tree. </p>
|
||
|
|
||
|
</div>
|
||
|
</div>
|
||
|
<a class="anchor" id="ac1fa605c93d39433312ddaf7a8e9e7ff"></a>
|
||
|
<div class="memitem">
|
||
|
<div class="memproto">
|
||
|
<table class="memname">
|
||
|
<tr>
|
||
|
<td class="memname">std::string geos::index::quadtree::Quadtree::toString </td>
|
||
|
<td>(</td>
|
||
|
<td class="paramname"></td><td>)</td>
|
||
|
<td> const</td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</div><div class="memdoc">
|
||
|
|
||
|
</div>
|
||
|
</div>
|
||
|
<h2 class="groupheader">Member Data Documentation</h2>
|
||
|
<a class="anchor" id="a1bf75998e2b71ee8350ad292f23758ff"></a>
|
||
|
<div class="memitem">
|
||
|
<div class="memproto">
|
||
|
<table class="mlabels">
|
||
|
<tr>
|
||
|
<td class="mlabels-left">
|
||
|
<table class="memname">
|
||
|
<tr>
|
||
|
<td class="memname">double geos::index::quadtree::Quadtree::minExtent</td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</td>
|
||
|
<td class="mlabels-right">
|
||
|
<span class="mlabels"><span class="mlabel">private</span></span> </td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</div><div class="memdoc">
|
||
|
<p>Statistics</p>
|
||
|
<p>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. </p>
|
||
|
|
||
|
<p>Definition at line <a class="el" href="Quadtree_8h_source.html#l00092">92</a> of file <a class="el" href="Quadtree_8h_source.html">Quadtree.h</a>.</p>
|
||
|
|
||
|
</div>
|
||
|
</div>
|
||
|
<a class="anchor" id="aef9905e39e63473c525ab6970b9a6d6f"></a>
|
||
|
<div class="memitem">
|
||
|
<div class="memproto">
|
||
|
<table class="mlabels">
|
||
|
<tr>
|
||
|
<td class="mlabels-left">
|
||
|
<table class="memname">
|
||
|
<tr>
|
||
|
<td class="memname">std::vector<std::unique_ptr<<a class="el" href="classgeos_1_1geom_1_1Envelope.html">geom::Envelope</a>> > geos::index::quadtree::Quadtree::newEnvelopes</td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</td>
|
||
|
<td class="mlabels-right">
|
||
|
<span class="mlabels"><span class="mlabel">private</span></span> </td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</div><div class="memdoc">
|
||
|
|
||
|
<p>Definition at line <a class="el" href="Quadtree_8h_source.html#l00075">75</a> of file <a class="el" href="Quadtree_8h_source.html">Quadtree.h</a>.</p>
|
||
|
|
||
|
</div>
|
||
|
</div>
|
||
|
<a class="anchor" id="ac0082e2d5d3525f90c61e25bb6093489"></a>
|
||
|
<div class="memitem">
|
||
|
<div class="memproto">
|
||
|
<table class="mlabels">
|
||
|
<tr>
|
||
|
<td class="mlabels-left">
|
||
|
<table class="memname">
|
||
|
<tr>
|
||
|
<td class="memname"><a class="el" href="classgeos_1_1index_1_1quadtree_1_1Root.html">Root</a> geos::index::quadtree::Quadtree::root</td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</td>
|
||
|
<td class="mlabels-right">
|
||
|
<span class="mlabels"><span class="mlabel">private</span></span> </td>
|
||
|
</tr>
|
||
|
</table>
|
||
|
</div><div class="memdoc">
|
||
|
|
||
|
<p>Definition at line <a class="el" href="Quadtree_8h_source.html#l00079">79</a> of file <a class="el" href="Quadtree_8h_source.html">Quadtree.h</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><!-- contents -->
|
||
|
<!-- start footer part -->
|
||
|
<hr class="footer"/><address class="footer"><small>
|
||
|
Generated by  <a href="http://www.doxygen.org/index.html">
|
||
|
<img class="footer" src="doxygen.png" alt="doxygen"/>
|
||
|
</a> 1.8.11
|
||
|
</small></address>
|
||
|
</body>
|
||
|
</html>
|