<!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>OGR: cpl_quad_tree.h File 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.6.2-20100208 -->
<div class="navigation" id="top">
<div class="tabs">
<ul>
<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>
<li><a href="dirs.html"><span>Directories</span></a></li>
</ul>
</div>
<div class="tabs">
<ul>
<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 class="navpath"><a class="el" href="dir_9403295bfc17f2c2ba80cf17b83e4de3.html">port</a>
</div>
</div>
<div class="contents">
<h1>cpl_quad_tree.h File Reference</h1><code>#include "<a class="el" href="cpl__port_8h_source.html">cpl_port.h</a>"</code><br/>
<p><a href="cpl__quad__tree_8h_source.html">Go to the source code of this file.</a></p>
<table border="0" cellpadding="0" cellspacing="0">
<tr><td colspan="2"><h2>Classes</h2></td></tr>
<tr><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><td colspan="2"><h2>Functions</h2></td></tr>
<tr><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><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><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><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><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><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><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><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>
</table>
<hr/><a name="_details"></a><h2>Detailed Description</h2>
<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>
<hr/><h2>Function Documentation</h2>
<a class="anchor" id="a0b487ddebd63f9c8b63a8fdd3bf3c301"></a><!-- doxytag: member="cpl_quad_tree.h::CPLQuadTreeCreate" ref="a0b487ddebd63f9c8b63a8fdd3bf3c301" args="(const CPLRectObj *pGlobalBounds, CPLQuadTreeGetBoundsFunc pfnGetBounds)" -->
<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><td> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td><td></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Create a new quadtree</p>
<dl><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>pGlobalBounds</em> </td><td>a pointer to the global extent of all the elements that will be inserted </td></tr>
<tr><td valign="top"></td><td valign="top"><em>pfnGetBounds</em> </td><td>a user provided function to get the bounding box of the inserted elements</td></tr>
</table>
</dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>a newly allocated quadtree </dd></dl>
</div>
</div>
<a class="anchor" id="a9320655fe1098286848b8d5ef093c887"></a><!-- doxytag: member="cpl_quad_tree.h::CPLQuadTreeDestroy" ref="a9320655fe1098286848b8d5ef093c887" args="(CPLQuadTree *hQuadtree)" -->
<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><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>hQuadTree</em> </td><td>the quad tree to destroy </td></tr>
</table>
</dd>
</dl>
</div>
</div>
<a class="anchor" id="a82f2bf8319af180e966f22900d54e980"></a><!-- doxytag: member="cpl_quad_tree.h::CPLQuadTreeForeach" ref="a82f2bf8319af180e966f22900d54e980" args="(const CPLQuadTree *hQuadtree, CPLQuadTreeForeachFunc pfnForeach, void *pUserData)" -->
<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><td> </td>
</tr>
<tr>
<td></td>
<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 *NOT* be modified during the walk.</p>
<dl><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>hQuadTree</em> </td><td>the quad tree </td></tr>
<tr><td valign="top"></td><td valign="top"><em>pfnForeach</em> </td><td>the function called on each element. </td></tr>
<tr><td valign="top"></td><td valign="top"><em>pUserData</em> </td><td>the user data provided to the function. </td></tr>
</table>
</dd>
</dl>
</div>
</div>
<a class="anchor" id="afef1c2bed768bfd767d1e9f7ae6fd03a"></a><!-- doxytag: member="cpl_quad_tree.h::CPLQuadTreeGetAdvisedMaxDepth" ref="afef1c2bed768bfd767d1e9f7ae6fd03a" args="(int nExpectedFeatures)" -->
<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><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>nExpectedFeatures</em> </td><td>the expected maximum number of elements to be inserted</td></tr>
</table>
</dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>the optimal depth of a quadtree to hold nExpectedFeatures </dd></dl>
</div>
</div>
<a class="anchor" id="a39343477b5c8ea861d122a9925e64a2d"></a><!-- doxytag: member="cpl_quad_tree.h::CPLQuadTreeInsert" ref="a39343477b5c8ea861d122a9925e64a2d" args="(CPLQuadTree *hQuadtree, void *hFeature)" -->
<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><td> </td>
</tr>
<tr>
<td></td>
<td>)</td>
<td></td><td></td><td></td>
</tr>
</table>
</div>
<div class="memdoc">
<p>Insert a feature into a quadtree</p>
<dl><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>hQuadTree</em> </td><td>the quad tree </td></tr>
<tr><td valign="top"></td><td valign="top"><em>hFeature</em> </td><td>the feature to insert </td></tr>
</table>
</dd>
</dl>
</div>
</div>
<a class="anchor" id="af75a68e7c26168ace2c21a55dc7827d3"></a><!-- doxytag: member="cpl_quad_tree.h::CPLQuadTreeSearch" ref="af75a68e7c26168ace2c21a55dc7827d3" args="(const CPLQuadTree *hQuadtree, const CPLRectObj *pAoi, int *pnFeatureCount)" -->
<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><td> </td>
</tr>
<tr>
<td></td>
<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><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>hQuadTree</em> </td><td>the quad tree </td></tr>
<tr><td valign="top"></td><td valign="top"><em>pAoi</em> </td><td>the pointer to the area of interest </td></tr>
<tr><td valign="top"></td><td valign="top"><em>pnFeatureCount</em> </td><td>the user data provided to the function.</td></tr>
</table>
</dd>
</dl>
<dl class="return"><dt><b>Returns:</b></dt><dd>an array of features that must be freed with CPLFree </dd></dl>
</div>
</div>
<a class="anchor" id="a85d74680199da83b9b60565d2ebe05d6"></a><!-- doxytag: member="cpl_quad_tree.h::CPLQuadTreeSetBucketCapacity" ref="a85d74680199da83b9b60565d2ebe05d6" args="(CPLQuadTree *hQuadtree, int nBucketCapacity)" -->
<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><td> </td>
</tr>
<tr>
<td></td>
<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><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>hQuadTree</em> </td><td>the quad tree </td></tr>
<tr><td valign="top"></td><td valign="top"><em>nBucketCapacity</em> </td><td>the maximum capactiy of a node of a quadtree </td></tr>
</table>
</dd>
</dl>
</div>
</div>
<a class="anchor" id="a86b9aafba094be796df843a3c0cb2c67"></a><!-- doxytag: member="cpl_quad_tree.h::CPLQuadTreeSetMaxDepth" ref="a86b9aafba094be796df843a3c0cb2c67" args="(CPLQuadTree *hQuadtree, int nMaxDepth)" -->
<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><td> </td>
</tr>
<tr>
<td></td>
<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><dt><b>Parameters:</b></dt><dd>
<table border="0" cellspacing="2" cellpadding="0">
<tr><td valign="top"></td><td valign="top"><em>hQuadTree</em> </td><td>the quad tree </td></tr>
<tr><td valign="top"></td><td valign="top"><em>nMaxDepth</em> </td><td>the maximum depth allowed </td></tr>
</table>
</dd>
</dl>
</div>
</div>
</div>
<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.6.2-20100208.
</body>
</html>
