EVOLUTION-MANAGER
Edit File: cpl__quad__tree_8h.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.5"/> <title>OGR: cpl_quad_tree.h File 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 style="padding-left: 0.5em;"> <div id="projectname">OGR </div> </td> </tr> </tbody> </table> </div> <!-- end header part --> <!-- Generated by Doxygen 1.8.5 --> <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="annotated.html"><span>Classes</span></a></li> <li class="current"><a href="files.html"><span>Files</span></a></li> </ul> </div> <div id="navrow2" class="tabs2"> <ul class="tablist"> <li><a href="files.html"><span>File List</span></a></li> <li><a href="globals.html"><span>File Members</span></a></li> </ul> </div> <div id="nav-path" class="navpath"> <ul> <li class="navelem"><a class="el" href="dir_651562d8bf6cfd3e81eff5b570d7df50.html">port</a></li> </ul> </div> </div><!-- top --> <div class="header"> <div class="summary"> <a href="#nested-classes">Classes</a> | <a href="#func-members">Functions</a> </div> <div class="headertitle"> <div class="title">cpl_quad_tree.h File Reference</div> </div> </div><!--header--> <div class="contents"> <div class="textblock"><code>#include "<a class="el" href="cpl__port_8h_source.html">cpl_port.h</a>"</code><br/> </div> <p><a href="cpl__quad__tree_8h_source.html">Go to the source code of this file.</a></p> <table class="memberdecls"> <tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="nested-classes"></a> Classes</h2></td></tr> <tr class="memitem:"><td class="memItemLeft" align="right" valign="top">struct  </td><td class="memItemRight" valign="bottom"><a class="el" href="structCPLRectObj.html">CPLRectObj</a></td></tr> <tr class="separator:"><td class="memSeparator" colspan="2"> </td></tr> </table><table class="memberdecls"> <tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="func-members"></a> Functions</h2></td></tr> <tr class="memitem:a0b487ddebd63f9c8b63a8fdd3bf3c301"><td class="memItemLeft" align="right" valign="top"><a class="el" href="struct__CPLQuadTree.html">CPLQuadTree</a> * </td><td class="memItemRight" valign="bottom"><a class="el" href="cpl__quad__tree_8h.html#a0b487ddebd63f9c8b63a8fdd3bf3c301">CPLQuadTreeCreate</a> (const <a class="el" href="structCPLRectObj.html">CPLRectObj</a> *pGlobalBounds, CPLQuadTreeGetBoundsFunc pfnGetBounds)</td></tr> <tr class="separator:a0b487ddebd63f9c8b63a8fdd3bf3c301"><td class="memSeparator" colspan="2"> </td></tr> <tr class="memitem:a9320655fe1098286848b8d5ef093c887"><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="cpl__quad__tree_8h.html#a9320655fe1098286848b8d5ef093c887">CPLQuadTreeDestroy</a> (<a class="el" href="struct__CPLQuadTree.html">CPLQuadTree</a> *hQuadtree)</td></tr> <tr class="separator:a9320655fe1098286848b8d5ef093c887"><td class="memSeparator" colspan="2"> </td></tr> <tr class="memitem:a85d74680199da83b9b60565d2ebe05d6"><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="cpl__quad__tree_8h.html#a85d74680199da83b9b60565d2ebe05d6">CPLQuadTreeSetBucketCapacity</a> (<a class="el" href="struct__CPLQuadTree.html">CPLQuadTree</a> *hQuadtree, int nBucketCapacity)</td></tr> <tr class="separator:a85d74680199da83b9b60565d2ebe05d6"><td class="memSeparator" colspan="2"> </td></tr> <tr class="memitem:afef1c2bed768bfd767d1e9f7ae6fd03a"><td class="memItemLeft" align="right" valign="top">int </td><td class="memItemRight" valign="bottom"><a class="el" href="cpl__quad__tree_8h.html#afef1c2bed768bfd767d1e9f7ae6fd03a">CPLQuadTreeGetAdvisedMaxDepth</a> (int nExpectedFeatures)</td></tr> <tr class="separator:afef1c2bed768bfd767d1e9f7ae6fd03a"><td class="memSeparator" colspan="2"> </td></tr> <tr class="memitem:a86b9aafba094be796df843a3c0cb2c67"><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="cpl__quad__tree_8h.html#a86b9aafba094be796df843a3c0cb2c67">CPLQuadTreeSetMaxDepth</a> (<a class="el" href="struct__CPLQuadTree.html">CPLQuadTree</a> *hQuadtree, int nMaxDepth)</td></tr> <tr class="separator:a86b9aafba094be796df843a3c0cb2c67"><td class="memSeparator" colspan="2"> </td></tr> <tr class="memitem:a39343477b5c8ea861d122a9925e64a2d"><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="cpl__quad__tree_8h.html#a39343477b5c8ea861d122a9925e64a2d">CPLQuadTreeInsert</a> (<a class="el" href="struct__CPLQuadTree.html">CPLQuadTree</a> *hQuadtree, void *hFeature)</td></tr> <tr class="separator:a39343477b5c8ea861d122a9925e64a2d"><td class="memSeparator" colspan="2"> </td></tr> <tr class="memitem:aa8aee05f03dcfe14a39a486913bb3709"><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="cpl__quad__tree_8h.html#aa8aee05f03dcfe14a39a486913bb3709">CPLQuadTreeInsertWithBounds</a> (<a class="el" href="struct__CPLQuadTree.html">CPLQuadTree</a> *hQuadtree, void *hFeature, const <a class="el" href="structCPLRectObj.html">CPLRectObj</a> *psBounds)</td></tr> <tr class="separator:aa8aee05f03dcfe14a39a486913bb3709"><td class="memSeparator" colspan="2"> </td></tr> <tr class="memitem:af75a68e7c26168ace2c21a55dc7827d3"><td class="memItemLeft" align="right" valign="top">void ** </td><td class="memItemRight" valign="bottom"><a class="el" href="cpl__quad__tree_8h.html#af75a68e7c26168ace2c21a55dc7827d3">CPLQuadTreeSearch</a> (const <a class="el" href="struct__CPLQuadTree.html">CPLQuadTree</a> *hQuadtree, const <a class="el" href="structCPLRectObj.html">CPLRectObj</a> *pAoi, int *pnFeatureCount)</td></tr> <tr class="separator:af75a68e7c26168ace2c21a55dc7827d3"><td class="memSeparator" colspan="2"> </td></tr> <tr class="memitem:a82f2bf8319af180e966f22900d54e980"><td class="memItemLeft" align="right" valign="top">void </td><td class="memItemRight" valign="bottom"><a class="el" href="cpl__quad__tree_8h.html#a82f2bf8319af180e966f22900d54e980">CPLQuadTreeForeach</a> (const <a class="el" href="struct__CPLQuadTree.html">CPLQuadTree</a> *hQuadtree, CPLQuadTreeForeachFunc pfnForeach, void *pUserData)</td></tr> <tr class="separator:a82f2bf8319af180e966f22900d54e980"><td class="memSeparator" colspan="2"> </td></tr> </table> <a name="details" id="details"></a><h2 class="groupheader">Detailed Description</h2> <div class="textblock"><p>Quad tree implementation.</p> <p>A quadtree is a tree data structure in which each internal node has up to four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions </p> </div><h2 class="groupheader">Function Documentation</h2> <a class="anchor" id="a0b487ddebd63f9c8b63a8fdd3bf3c301"></a> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname"><a class="el" href="struct__CPLQuadTree.html">CPLQuadTree</a>* CPLQuadTreeCreate </td> <td>(</td> <td class="paramtype">const <a class="el" href="structCPLRectObj.html">CPLRectObj</a> * </td> <td class="paramname"><em>pGlobalBounds</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype">CPLQuadTreeGetBoundsFunc </td> <td class="paramname"><em>pfnGetBounds</em> </td> </tr> <tr> <td></td> <td>)</td> <td></td><td></td> </tr> </table> </div><div class="memdoc"> <p>Create a new quadtree</p> <dl class="params"><dt>Parameters</dt><dd> <table class="params"> <tr><td class="paramname">pGlobalBounds</td><td>a pointer to the global extent of all the elements that will be inserted </td></tr> <tr><td class="paramname">pfnGetBounds</td><td>a user provided function to get the bounding box of the inserted elements. If it is set to NULL, then <a class="el" href="cpl__quad__tree_8h.html#aa8aee05f03dcfe14a39a486913bb3709">CPLQuadTreeInsertWithBounds()</a> must be used, and extra memory will be used to keep features bounds in the quad tree.</td></tr> </table> </dd> </dl> <dl class="section return"><dt>Returns</dt><dd>a newly allocated quadtree </dd></dl> <p>References <a class="el" href="cpl__conv_8h.html#a9ebcdb25fc6ff90b0c7b01733d5ae6d3">CPLMalloc()</a>.</p> </div> </div> <a class="anchor" id="a9320655fe1098286848b8d5ef093c887"></a> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">void CPLQuadTreeDestroy </td> <td>(</td> <td class="paramtype"><a class="el" href="struct__CPLQuadTree.html">CPLQuadTree</a> * </td> <td class="paramname"><em>hQuadTree</em></td><td>)</td> <td></td> </tr> </table> </div><div class="memdoc"> <p>Destroy a quadtree</p> <dl class="params"><dt>Parameters</dt><dd> <table class="params"> <tr><td class="paramname">hQuadTree</td><td>the quad tree to destroy </td></tr> </table> </dd> </dl> </div> </div> <a class="anchor" id="a82f2bf8319af180e966f22900d54e980"></a> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">void CPLQuadTreeForeach </td> <td>(</td> <td class="paramtype">const <a class="el" href="struct__CPLQuadTree.html">CPLQuadTree</a> * </td> <td class="paramname"><em>hQuadTree</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype">CPLQuadTreeForeachFunc </td> <td class="paramname"><em>pfnForeach</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype">void * </td> <td class="paramname"><em>pUserData</em> </td> </tr> <tr> <td></td> <td>)</td> <td></td><td></td> </tr> </table> </div><div class="memdoc"> <p>Walk through the quadtree and runs the provided function on all the elements</p> <p>This function is provided with the user_data argument of pfnForeach. It must return TRUE to go on the walk through the hash set, or FALSE to make it stop.</p> <p>Note : the structure of the quadtree must <em>NOT</em> be modified during the walk.</p> <dl class="params"><dt>Parameters</dt><dd> <table class="params"> <tr><td class="paramname">hQuadTree</td><td>the quad tree </td></tr> <tr><td class="paramname">pfnForeach</td><td>the function called on each element. </td></tr> <tr><td class="paramname">pUserData</td><td>the user data provided to the function. </td></tr> </table> </dd> </dl> </div> </div> <a class="anchor" id="afef1c2bed768bfd767d1e9f7ae6fd03a"></a> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">int CPLQuadTreeGetAdvisedMaxDepth </td> <td>(</td> <td class="paramtype">int </td> <td class="paramname"><em>nExpectedFeatures</em></td><td>)</td> <td></td> </tr> </table> </div><div class="memdoc"> <p>Returns the optimal depth of a quadtree to hold nExpectedFeatures</p> <dl class="params"><dt>Parameters</dt><dd> <table class="params"> <tr><td class="paramname">nExpectedFeatures</td><td>the expected maximum number of elements to be inserted</td></tr> </table> </dd> </dl> <dl class="section return"><dt>Returns</dt><dd>the optimal depth of a quadtree to hold nExpectedFeatures </dd></dl> <p>References <a class="el" href="cpl__error_8h.html#ad0c5d3481dd34c1f3a0f7775ebf74817">CPLDebug()</a>.</p> </div> </div> <a class="anchor" id="a39343477b5c8ea861d122a9925e64a2d"></a> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">void CPLQuadTreeInsert </td> <td>(</td> <td class="paramtype"><a class="el" href="struct__CPLQuadTree.html">CPLQuadTree</a> * </td> <td class="paramname"><em>hQuadTree</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype">void * </td> <td class="paramname"><em>hFeature</em> </td> </tr> <tr> <td></td> <td>)</td> <td></td><td></td> </tr> </table> </div><div class="memdoc"> <p>Insert a feature into a quadtree</p> <dl class="params"><dt>Parameters</dt><dd> <table class="params"> <tr><td class="paramname">hQuadTree</td><td>the quad tree </td></tr> <tr><td class="paramname">hFeature</td><td>the feature to insert </td></tr> </table> </dd> </dl> <p>References <a class="el" href="cpl__error_8h.html#aad2b98dd58e4de706a245faddac90403">CPLError()</a>.</p> </div> </div> <a class="anchor" id="aa8aee05f03dcfe14a39a486913bb3709"></a> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">void CPLQuadTreeInsertWithBounds </td> <td>(</td> <td class="paramtype"><a class="el" href="struct__CPLQuadTree.html">CPLQuadTree</a> * </td> <td class="paramname"><em>hQuadTree</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype">void * </td> <td class="paramname"><em>hFeature</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype">const <a class="el" href="structCPLRectObj.html">CPLRectObj</a> * </td> <td class="paramname"><em>psBounds</em> </td> </tr> <tr> <td></td> <td>)</td> <td></td><td></td> </tr> </table> </div><div class="memdoc"> <p>Insert a feature into a quadtree</p> <dl class="params"><dt>Parameters</dt><dd> <table class="params"> <tr><td class="paramname">hQuadTree</td><td>the quad tree </td></tr> <tr><td class="paramname">hFeature</td><td>the feature to insert </td></tr> <tr><td class="paramname">psBounds</td><td>bounds of the feature </td></tr> </table> </dd> </dl> </div> </div> <a class="anchor" id="af75a68e7c26168ace2c21a55dc7827d3"></a> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">void** CPLQuadTreeSearch </td> <td>(</td> <td class="paramtype">const <a class="el" href="struct__CPLQuadTree.html">CPLQuadTree</a> * </td> <td class="paramname"><em>hQuadTree</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype">const <a class="el" href="structCPLRectObj.html">CPLRectObj</a> * </td> <td class="paramname"><em>pAoi</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype">int * </td> <td class="paramname"><em>pnFeatureCount</em> </td> </tr> <tr> <td></td> <td>)</td> <td></td><td></td> </tr> </table> </div><div class="memdoc"> <p>Returns all the elements inserted whose bounding box intersects the provided area of interest</p> <dl class="params"><dt>Parameters</dt><dd> <table class="params"> <tr><td class="paramname">hQuadTree</td><td>the quad tree </td></tr> <tr><td class="paramname">pAoi</td><td>the pointer to the area of interest </td></tr> <tr><td class="paramname">pnFeatureCount</td><td>the user data provided to the function.</td></tr> </table> </dd> </dl> <dl class="section return"><dt>Returns</dt><dd>an array of features that must be freed with CPLFree </dd></dl> </div> </div> <a class="anchor" id="a85d74680199da83b9b60565d2ebe05d6"></a> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">void CPLQuadTreeSetBucketCapacity </td> <td>(</td> <td class="paramtype"><a class="el" href="struct__CPLQuadTree.html">CPLQuadTree</a> * </td> <td class="paramname"><em>hQuadTree</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype">int </td> <td class="paramname"><em>nBucketCapacity</em> </td> </tr> <tr> <td></td> <td>)</td> <td></td><td></td> </tr> </table> </div><div class="memdoc"> <p>Set the maximum capacity of a node of a quadtree. The default value is 8. Note that the maximum capacity will only be honoured if the features inserted have a point geometry. Otherwise it may be exceeded.</p> <dl class="params"><dt>Parameters</dt><dd> <table class="params"> <tr><td class="paramname">hQuadTree</td><td>the quad tree </td></tr> <tr><td class="paramname">nBucketCapacity</td><td>the maximum capactiy of a node of a quadtree </td></tr> </table> </dd> </dl> </div> </div> <a class="anchor" id="a86b9aafba094be796df843a3c0cb2c67"></a> <div class="memitem"> <div class="memproto"> <table class="memname"> <tr> <td class="memname">void CPLQuadTreeSetMaxDepth </td> <td>(</td> <td class="paramtype"><a class="el" href="struct__CPLQuadTree.html">CPLQuadTree</a> * </td> <td class="paramname"><em>hQuadTree</em>, </td> </tr> <tr> <td class="paramkey"></td> <td></td> <td class="paramtype">int </td> <td class="paramname"><em>nMaxDepth</em> </td> </tr> <tr> <td></td> <td>)</td> <td></td><td></td> </tr> </table> </div><div class="memdoc"> <p>Set the maximum depth of a quadtree. By default, quad trees have no maximum depth, but a maximum bucket capacity.</p> <dl class="params"><dt>Parameters</dt><dd> <table class="params"> <tr><td class="paramname">hQuadTree</td><td>the quad tree </td></tr> <tr><td class="paramname">nMaxDepth</td><td>the maximum depth allowed </td></tr> </table> </dd> </dl> </div> </div> </div><!-- contents --> <hr> Generated for GDAL by <a href="http://www.doxygen.org/index.html"><img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.8.5. </body> </html>