<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=iso-8859-1">
<title>nanoflann.hpp Source File</title>
<link href="doxygen.css" rel="stylesheet" type="text/css">
<link href="tabs.css" rel="stylesheet" type="text/css">
</head><body>
<div align="left"><a href="http://www.mrpt.org/">Main MRPT website</a> > <b>C++ reference</b> </div>
<div align="right">
<a href="index.html"><img border="0" src="mrpt_logo.png" alt="MRPT logo"></a>
</div>
<!-- Generated by Doxygen 1.7.5 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
<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="modules.html"><span>Modules</span></a></li>
<li><a href="namespaces.html"><span>Namespaces</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>
<div id="MSearchBox" class="MSearchBoxInactive">
<div class="left">
<form id="FSearchBox" action="search.php" method="get">
<img id="MSearchSelect" src="search/mag.png" alt=""/>
<input type="text" id="MSearchField" name="query" value="Search" size="20" accesskey="S"
onfocus="searchBox.OnSearchFieldFocus(true)"
onblur="searchBox.OnSearchFieldFocus(false)"/>
</form>
</div><div class="right"></div>
</div>
</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 class="header">
<div class="headertitle">
<div class="title">nanoflann.hpp</div> </div>
</div>
<div class="contents">
<a href="nanoflann_8hpp.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/***********************************************************************</span>
<a name="l00002"></a>00002 <span class="comment"> * Software License Agreement (BSD License)</span>
<a name="l00003"></a>00003 <span class="comment"> *</span>
<a name="l00004"></a>00004 <span class="comment"> * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved.</span>
<a name="l00005"></a>00005 <span class="comment"> * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). All rights reserved.</span>
<a name="l00006"></a>00006 <span class="comment"> * Copyright 2011 Jose Luis Blanco (joseluisblancoc@gmail.com).</span>
<a name="l00007"></a>00007 <span class="comment"> * All rights reserved.</span>
<a name="l00008"></a>00008 <span class="comment"> *</span>
<a name="l00009"></a>00009 <span class="comment"> * THE BSD LICENSE</span>
<a name="l00010"></a>00010 <span class="comment"> *</span>
<a name="l00011"></a>00011 <span class="comment"> * Redistribution and use in source and binary forms, with or without</span>
<a name="l00012"></a>00012 <span class="comment"> * modification, are permitted provided that the following conditions</span>
<a name="l00013"></a>00013 <span class="comment"> * are met:</span>
<a name="l00014"></a>00014 <span class="comment"> *</span>
<a name="l00015"></a>00015 <span class="comment"> * 1. Redistributions of source code must retain the above copyright</span>
<a name="l00016"></a>00016 <span class="comment"> * notice, this list of conditions and the following disclaimer.</span>
<a name="l00017"></a>00017 <span class="comment"> * 2. Redistributions in binary form must reproduce the above copyright</span>
<a name="l00018"></a>00018 <span class="comment"> * notice, this list of conditions and the following disclaimer in the</span>
<a name="l00019"></a>00019 <span class="comment"> * documentation and/or other materials provided with the distribution.</span>
<a name="l00020"></a>00020 <span class="comment"> *</span>
<a name="l00021"></a>00021 <span class="comment"> * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR</span>
<a name="l00022"></a>00022 <span class="comment"> * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES</span>
<a name="l00023"></a>00023 <span class="comment"> * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.</span>
<a name="l00024"></a>00024 <span class="comment"> * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,</span>
<a name="l00025"></a>00025 <span class="comment"> * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT</span>
<a name="l00026"></a>00026 <span class="comment"> * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,</span>
<a name="l00027"></a>00027 <span class="comment"> * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY</span>
<a name="l00028"></a>00028 <span class="comment"> * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT</span>
<a name="l00029"></a>00029 <span class="comment"> * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF</span>
<a name="l00030"></a>00030 <span class="comment"> * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.</span>
<a name="l00031"></a>00031 <span class="comment"> *************************************************************************/</span>
<a name="l00032"></a>00032
<a name="l00033"></a>00033 <span class="preprocessor">#ifndef NANOFLANN_HPP_</span>
<a name="l00034"></a>00034 <span class="preprocessor"></span><span class="preprocessor">#define NANOFLANN_HPP_</span>
<a name="l00035"></a>00035 <span class="preprocessor"></span>
<a name="l00036"></a>00036 <span class="preprocessor">#include <vector></span>
<a name="l00037"></a>00037 <span class="preprocessor">#include <string></span>
<a name="l00038"></a>00038 <span class="preprocessor">#include <cassert></span>
<a name="l00039"></a>00039 <span class="preprocessor">#include <map></span>
<a name="l00040"></a>00040 <span class="preprocessor">#include <algorithm></span>
<a name="l00041"></a>00041 <span class="preprocessor">#include <stdexcept></span>
<a name="l00042"></a>00042 <span class="preprocessor">#include <limits></span>
<a name="l00043"></a>00043
<a name="l00044"></a>00044 <span class="preprocessor">#include <cassert></span>
<a name="l00045"></a>00045 <span class="preprocessor">#include <cstring></span>
<a name="l00046"></a>00046 <span class="preprocessor">#include <cstdio></span>
<a name="l00047"></a>00047 <span class="preprocessor">#include <cmath></span>
<a name="l00048"></a>00048
<a name="l00049"></a>00049
<a name="l00050"></a><a class="code" href="namespacenanoflann.html">00050</a> <span class="keyword">namespace </span>nanoflann
<a name="l00051"></a>00051 {<span class="comment"></span>
<a name="l00052"></a>00052 <span class="comment">/** @addtogroup nanoflann_grp nanoflann C++ library for ANN</span>
<a name="l00053"></a>00053 <span class="comment"> * @{ */</span>
<a name="l00054"></a>00054 <span class="comment"></span>
<a name="l00055"></a>00055 <span class="comment"> /** Library version: 0xMmP (M=Major,m=minor,P=path) */</span>
<a name="l00056"></a><a class="code" href="group__nanoflann__grp.html#ga7b8efca796d8e1861a432a5f6b8404a1">00056</a> <span class="preprocessor"> #define NANOFLANN_VERSION 0x101</span>
<a name="l00057"></a>00057 <span class="preprocessor"></span><span class="comment"></span>
<a name="l00058"></a>00058 <span class="comment"> /** @addtogroup result_sets_grp Result set classes</span>
<a name="l00059"></a>00059 <span class="comment"> * @{ */</span>
<a name="l00060"></a>00060 <span class="keyword">template</span> <<span class="keyword">typename</span> DistanceType>
<a name="l00061"></a>00061 <span class="keyword">class </span>KNNResultSet
<a name="l00062"></a>00062 {
<a name="l00063"></a><a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a58b9f55e058b6bea9d5cd0e84a5bb713">00063</a> <span class="keywordtype">int</span>* <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a58b9f55e058b6bea9d5cd0e84a5bb713">indices</a>;
<a name="l00064"></a><a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a9e5955301b936a6ba02bf179201a0793">00064</a> DistanceType* <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a9e5955301b936a6ba02bf179201a0793">dists</a>;
<a name="l00065"></a><a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#ab5250707a62f83ee58c2e818cd9edceb">00065</a> <span class="keywordtype">int</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#ab5250707a62f83ee58c2e818cd9edceb">capacity</a>;
<a name="l00066"></a><a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">00066</a> <span class="keywordtype">int</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">count</a>;
<a name="l00067"></a>00067
<a name="l00068"></a>00068 <span class="keyword">public</span>:
<a name="l00069"></a><a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a75ab4e269ddf954e191cb6d300e1aba9">00069</a> <span class="keyword">inline</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a75ab4e269ddf954e191cb6d300e1aba9">KNNResultSet</a>(<span class="keywordtype">int</span> capacity_) : <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#ab5250707a62f83ee58c2e818cd9edceb">capacity</a>(capacity_), <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">count</a>(0)
<a name="l00070"></a>00070 {
<a name="l00071"></a>00071 }
<a name="l00072"></a>00072
<a name="l00073"></a><a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a4fefecb0ff9480ceeb1212afa67f9966">00073</a> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a4fefecb0ff9480ceeb1212afa67f9966">init</a>(<span class="keywordtype">int</span>* indices_, DistanceType* dists_)
<a name="l00074"></a>00074 {
<a name="l00075"></a>00075 <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a58b9f55e058b6bea9d5cd0e84a5bb713">indices</a> = indices_;
<a name="l00076"></a>00076 <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a9e5955301b936a6ba02bf179201a0793">dists</a> = dists_;
<a name="l00077"></a>00077 <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">count</a> = 0;
<a name="l00078"></a>00078 <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a9e5955301b936a6ba02bf179201a0793">dists</a>[<a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#ab5250707a62f83ee58c2e818cd9edceb">capacity</a>-1] = (std::numeric_limits<DistanceType>::max)();
<a name="l00079"></a>00079 }
<a name="l00080"></a>00080
<a name="l00081"></a><a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a1ccd37d4307264f3c70abb55dc5d57e1">00081</a> <span class="keyword">inline</span> <span class="keywordtype">size_t</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a1ccd37d4307264f3c70abb55dc5d57e1">size</a>()<span class="keyword"> const</span>
<a name="l00082"></a>00082 <span class="keyword"> </span>{
<a name="l00083"></a>00083 <span class="keywordflow">return</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">count</a>;
<a name="l00084"></a>00084 }
<a name="l00085"></a>00085
<a name="l00086"></a><a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a064524057fbbb11d0376e781c414fb1b">00086</a> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a064524057fbbb11d0376e781c414fb1b">full</a>()<span class="keyword"> const</span>
<a name="l00087"></a>00087 <span class="keyword"> </span>{
<a name="l00088"></a>00088 <span class="keywordflow">return</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">count</a> == <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#ab5250707a62f83ee58c2e818cd9edceb">capacity</a>;
<a name="l00089"></a>00089 }
<a name="l00090"></a>00090
<a name="l00091"></a>00091
<a name="l00092"></a><a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#ac970d83afa10c78881af7c564a351919">00092</a> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#ac970d83afa10c78881af7c564a351919">addPoint</a>(DistanceType dist, <span class="keywordtype">int</span> index)
<a name="l00093"></a>00093 {
<a name="l00094"></a>00094 <span class="keywordtype">int</span> i;
<a name="l00095"></a>00095 <span class="keywordflow">for</span> (i=<a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">count</a>; i>0; --i) {
<a name="l00096"></a>00096 <span class="preprocessor">#ifdef NANOFLANN_FIRST_MATCH</span>
<a name="l00097"></a>00097 <span class="preprocessor"></span> <span class="keywordflow">if</span> ( (<a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a9e5955301b936a6ba02bf179201a0793">dists</a>[i-1]>dist) || ((dist==<a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a9e5955301b936a6ba02bf179201a0793">dists</a>[i-1])&&(<a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a58b9f55e058b6bea9d5cd0e84a5bb713">indices</a>[i-1]>index)) ) {
<a name="l00098"></a>00098 <span class="preprocessor">#else</span>
<a name="l00099"></a>00099 <span class="preprocessor"></span> <span class="keywordflow">if</span> (<a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a9e5955301b936a6ba02bf179201a0793">dists</a>[i-1]>dist) {
<a name="l00100"></a>00100 <span class="preprocessor">#endif</span>
<a name="l00101"></a>00101 <span class="preprocessor"></span> <span class="keywordflow">if</span> (i<<a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#ab5250707a62f83ee58c2e818cd9edceb">capacity</a>) {
<a name="l00102"></a>00102 <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a9e5955301b936a6ba02bf179201a0793">dists</a>[i] = <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a9e5955301b936a6ba02bf179201a0793">dists</a>[i-1];
<a name="l00103"></a>00103 <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a58b9f55e058b6bea9d5cd0e84a5bb713">indices</a>[i] = <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a58b9f55e058b6bea9d5cd0e84a5bb713">indices</a>[i-1];
<a name="l00104"></a>00104 }
<a name="l00105"></a>00105 }
<a name="l00106"></a>00106 <span class="keywordflow">else</span> <span class="keywordflow">break</span>;
<a name="l00107"></a>00107 }
<a name="l00108"></a>00108 <span class="keywordflow">if</span> (i<<a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#ab5250707a62f83ee58c2e818cd9edceb">capacity</a>) {
<a name="l00109"></a>00109 <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a9e5955301b936a6ba02bf179201a0793">dists</a>[i] = dist;
<a name="l00110"></a>00110 <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a58b9f55e058b6bea9d5cd0e84a5bb713">indices</a>[i] = index;
<a name="l00111"></a>00111 }
<a name="l00112"></a>00112 <span class="keywordflow">if</span> (<a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">count</a><<a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#ab5250707a62f83ee58c2e818cd9edceb">capacity</a>) <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">count</a>++;
<a name="l00113"></a>00113 }
<a name="l00114"></a>00114
<a name="l00115"></a><a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#aa8dc374e29496dd04cc03c0ba25ac667">00115</a> <span class="keyword">inline</span> DistanceType <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#aa8dc374e29496dd04cc03c0ba25ac667">worstDist</a>()<span class="keyword"> const</span>
<a name="l00116"></a>00116 <span class="keyword"> </span>{
<a name="l00117"></a>00117 <span class="keywordflow">return</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a9e5955301b936a6ba02bf179201a0793">dists</a>[<a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#ab5250707a62f83ee58c2e818cd9edceb">capacity</a>-1];
<a name="l00118"></a>00118 }
<a name="l00119"></a>00119 };
<a name="l00120"></a>00120
<a name="l00121"></a>00121 <span class="comment"></span>
<a name="l00122"></a>00122 <span class="comment"> /**</span>
<a name="l00123"></a>00123 <span class="comment"> * A result-set class used when performing a radius based search.</span>
<a name="l00124"></a>00124 <span class="comment"> */</span>
<a name="l00125"></a>00125 <span class="keyword">template</span> <<span class="keyword">typename</span> DistanceType>
<a name="l00126"></a>00126 <span class="keyword">class </span>RadiusResultSet
<a name="l00127"></a>00127 {
<a name="l00128"></a>00128 <span class="keyword">public</span>:
<a name="l00129"></a><a class="code" href="classnanoflann_1_1_radius_result_set.html#a7e6876092117bf7affedfbbd0227894e">00129</a> <span class="keyword">const</span> DistanceType <a class="code" href="classnanoflann_1_1_radius_result_set.html#a7e6876092117bf7affedfbbd0227894e">radius</a>;
<a name="l00130"></a>00130
<a name="l00131"></a><a class="code" href="classnanoflann_1_1_radius_result_set.html#a833e24da7b1d75daaa7d61db6339026f">00131</a> std::vector<std::pair<int,DistanceType> >& <a class="code" href="classnanoflann_1_1_radius_result_set.html#a833e24da7b1d75daaa7d61db6339026f">m_indices_dists</a>;
<a name="l00132"></a>00132
<a name="l00133"></a><a class="code" href="classnanoflann_1_1_radius_result_set.html#a308ef7a9be0fba3b9975984eae00cdf8">00133</a> <span class="keyword">inline</span> <a class="code" href="classnanoflann_1_1_radius_result_set.html" title="A result-set class used when performing a radius based search.">RadiusResultSet</a>(DistanceType radius_, <a class="code" href="classstd_1_1vector.html" title="STL class.">std::vector</a><std::pair<int,DistanceType> >& indices_dists) : radius(radius_), m_indices_dists(indices_dists)
<a name="l00134"></a>00134 {
<a name="l00135"></a>00135 <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a4fefecb0ff9480ceeb1212afa67f9966">init</a>();
<a name="l00136"></a>00136 }
<a name="l00137"></a>00137
<a name="l00138"></a><a class="code" href="classnanoflann_1_1_radius_result_set.html#a4d2d3a9c6a12484d07f207411fa8e40b">00138</a> <span class="keyword">inline</span> <a class="code" href="classnanoflann_1_1_radius_result_set.html#a4d2d3a9c6a12484d07f207411fa8e40b">~RadiusResultSet</a>() { }
<a name="l00139"></a>00139
<a name="l00140"></a><a class="code" href="classnanoflann_1_1_radius_result_set.html#a458a2d92b724cae73bc1ac9398670d72">00140</a> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="classnanoflann_1_1_radius_result_set.html#a458a2d92b724cae73bc1ac9398670d72">init</a>() { m_indices_dists.clear(); }
<a name="l00141"></a>00141
<a name="l00142"></a><a class="code" href="classnanoflann_1_1_radius_result_set.html#a66da0323665cfcc457d476c42e49ebcd">00142</a> <span class="keyword">inline</span> <span class="keywordtype">size_t</span> <a class="code" href="classnanoflann_1_1_radius_result_set.html#a66da0323665cfcc457d476c42e49ebcd">size</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> m_indices_dists.size(); }
<a name="l00143"></a>00143
<a name="l00144"></a><a class="code" href="classnanoflann_1_1_radius_result_set.html#a243f1585791dd56360cae8e5fe8c72bf">00144</a> <span class="keyword">inline</span> <span class="keywordtype">bool</span> <a class="code" href="classnanoflann_1_1_radius_result_set.html#a243f1585791dd56360cae8e5fe8c72bf">full</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> <span class="keyword">true</span>; }
<a name="l00145"></a>00145
<a name="l00146"></a><a class="code" href="classnanoflann_1_1_radius_result_set.html#ab895b4a98b696503473f6c682c1f7692">00146</a> <span class="keyword">inline</span> <span class="keywordtype">void</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#ac970d83afa10c78881af7c564a351919">addPoint</a>(DistanceType dist, <span class="keywordtype">int</span> index)
<a name="l00147"></a>00147 {
<a name="l00148"></a>00148 <span class="keywordflow">if</span> (dist<radius)
<a name="l00149"></a>00149 m_indices_dists.push_back(std::make_pair<int,DistanceType>(index,dist));
<a name="l00150"></a>00150 }
<a name="l00151"></a>00151
<a name="l00152"></a><a class="code" href="classnanoflann_1_1_radius_result_set.html#a1cd128776615a56187afa92caa84a0eb">00152</a> <span class="keyword">inline</span> DistanceType <a class="code" href="classnanoflann_1_1_radius_result_set.html#a1cd128776615a56187afa92caa84a0eb">worstDist</a>()<span class="keyword"> const </span>{ <span class="keywordflow">return</span> radius; }
<a name="l00153"></a>00153 };
<a name="l00154"></a>00154 <span class="comment"></span>
<a name="l00155"></a>00155 <span class="comment"> /** operator "<" for std::sort() */</span>
<a name="l00156"></a>00156 <span class="keyword">template</span> <<span class="keyword">typename</span> DistanceType>
<a name="l00157"></a>00157 <span class="keyword">struct </span>IndexDist_Sorter
<a name="l00158"></a>00158 {
<a name="l00159"></a><a class="code" href="structnanoflann_1_1_index_dist___sorter.html#a8796e860f9883f6943495efd2a77f87b">00159</a> <span class="keyword">inline</span> <span class="keywordtype">bool</span> operator()(<span class="keyword">const</span> std::pair<int,DistanceType> &p1, <span class="keyword">const</span> std::pair<int,DistanceType> &p2)<span class="keyword"> const</span>
<a name="l00160"></a>00160 <span class="keyword"> </span>{
<a name="l00161"></a>00161 <span class="keywordflow">return</span> p1.second < p2.second;
<a name="l00162"></a>00162 }
<a name="l00163"></a>00163 };
<a name="l00164"></a>00164 <span class="comment"></span>
<a name="l00165"></a>00165 <span class="comment"> /** @} */</span>
<a name="l00166"></a>00166
<a name="l00167"></a>00167 <span class="comment"></span>
<a name="l00168"></a>00168 <span class="comment"> /** @addtogroup loadsave_grp Load/save auxiliary functions</span>
<a name="l00169"></a>00169 <span class="comment"> * @{ */</span>
<a name="l00170"></a>00170 <span class="keyword">template</span><<span class="keyword">typename</span> T>
<a name="l00171"></a><a class="code" href="group__loadsave__grp.html#ga4eb2ec6a057da0c432ddc374800fc6ec">00171</a> <span class="keywordtype">void</span> <a class="code" href="group__loadsave__grp.html#ga4eb2ec6a057da0c432ddc374800fc6ec">save_value</a>(FILE* stream, <span class="keyword">const</span> T& value, <span class="keywordtype">int</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">count</a> = 1)
<a name="l00172"></a>00172 {
<a name="l00173"></a>00173 fwrite(&value, <span class="keyword">sizeof</span>(value),<a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">count</a>, stream);
<a name="l00174"></a>00174 }
<a name="l00175"></a>00175
<a name="l00176"></a>00176 <span class="keyword">template</span><<span class="keyword">typename</span> T>
<a name="l00177"></a><a class="code" href="group__loadsave__grp.html#gac767ee9c25febe0cd6af3ac2e186ffe7">00177</a> <span class="keywordtype">void</span> <a class="code" href="group__loadsave__grp.html#ga4eb2ec6a057da0c432ddc374800fc6ec">save_value</a>(FILE* stream, <span class="keyword">const</span> <a class="code" href="classstd_1_1vector.html">std::vector<T></a>& value)
<a name="l00178"></a>00178 {
<a name="l00179"></a>00179 <span class="keywordtype">size_t</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a1ccd37d4307264f3c70abb55dc5d57e1">size</a> = value.size();
<a name="l00180"></a>00180 fwrite(&size, <span class="keyword">sizeof</span>(<span class="keywordtype">size_t</span>), 1, stream);
<a name="l00181"></a>00181 fwrite(&value[0], <span class="keyword">sizeof</span>(T), size, stream);
<a name="l00182"></a>00182 }
<a name="l00183"></a>00183
<a name="l00184"></a>00184 <span class="keyword">template</span><<span class="keyword">typename</span> T>
<a name="l00185"></a><a class="code" href="group__loadsave__grp.html#ga8c271fd91a22446d477ef32aac2dce98">00185</a> <span class="keywordtype">void</span> <a class="code" href="group__loadsave__grp.html#ga8c271fd91a22446d477ef32aac2dce98">load_value</a>(FILE* stream, T& value, <span class="keywordtype">int</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">count</a> = 1)
<a name="l00186"></a>00186 {
<a name="l00187"></a>00187 <span class="keywordtype">int</span> read_cnt = fread(&value, <span class="keyword">sizeof</span>(value), <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">count</a>, stream);
<a name="l00188"></a>00188 <span class="keywordflow">if</span> (read_cnt != <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">count</a>) {
<a name="l00189"></a>00189 <span class="keywordflow">throw</span> <a class="code" href="classstd_1_1runtime__error.html" title="STL class.">std::runtime_error</a>(<span class="stringliteral">"Cannot read from file"</span>);
<a name="l00190"></a>00190 }
<a name="l00191"></a>00191 }
<a name="l00192"></a>00192
<a name="l00193"></a>00193
<a name="l00194"></a>00194 <span class="keyword">template</span><<span class="keyword">typename</span> T>
<a name="l00195"></a><a class="code" href="group__loadsave__grp.html#gaefed46e8576d6ce3f1796bb13387ad3d">00195</a> <span class="keywordtype">void</span> <a class="code" href="group__loadsave__grp.html#ga8c271fd91a22446d477ef32aac2dce98">load_value</a>(FILE* stream, <a class="code" href="classstd_1_1vector.html">std::vector<T></a>& value)
<a name="l00196"></a>00196 {
<a name="l00197"></a>00197 <span class="keywordtype">size_t</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a1ccd37d4307264f3c70abb55dc5d57e1">size</a>;
<a name="l00198"></a>00198 <span class="keywordtype">int</span> read_cnt = fread(&size, <span class="keyword">sizeof</span>(<span class="keywordtype">size_t</span>), 1, stream);
<a name="l00199"></a>00199 <span class="keywordflow">if</span> (read_cnt!=1) {
<a name="l00200"></a>00200 <span class="keywordflow">throw</span> <a class="code" href="classstd_1_1runtime__error.html" title="STL class.">std::runtime_error</a>(<span class="stringliteral">"Cannot read from file"</span>);
<a name="l00201"></a>00201 }
<a name="l00202"></a>00202 value.resize(size);
<a name="l00203"></a>00203 read_cnt = fread(&value[0], <span class="keyword">sizeof</span>(T), size, stream);
<a name="l00204"></a>00204 <span class="keywordflow">if</span> (read_cnt!=<span class="keywordtype">int</span>(size)) {
<a name="l00205"></a>00205 <span class="keywordflow">throw</span> <a class="code" href="classstd_1_1runtime__error.html" title="STL class.">std::runtime_error</a>(<span class="stringliteral">"Cannot read from file"</span>);
<a name="l00206"></a>00206 }
<a name="l00207"></a>00207 }<span class="comment"></span>
<a name="l00208"></a>00208 <span class="comment"> /** @} */</span>
<a name="l00209"></a>00209
<a name="l00210"></a>00210 <span class="comment"></span>
<a name="l00211"></a>00211 <span class="comment"> /** @addtogroup metric_grp Metric (distance) classes</span>
<a name="l00212"></a>00212 <span class="comment"> * @{ */</span>
<a name="l00213"></a>00213
<a name="l00214"></a><a class="code" href="group__metric__grp.html#gaf15608f8914516f8d949a8c053d55021">00214</a> <span class="keyword">template</span><<span class="keyword">typename</span> T> <span class="keyword">inline</span> T <a class="code" href="group__metric__grp.html#gaf15608f8914516f8d949a8c053d55021">abs</a>(T x) { <span class="keywordflow">return</span> (x<0) ? -x : x; }
<a name="l00215"></a><a class="code" href="group__metric__grp.html#ga5c50e8d34773da556210ad34d6157763">00215</a> <span class="keyword">template</span><> <span class="keyword">inline</span> <span class="keywordtype">int</span> <a class="code" href="group__metric__grp.html#ga5c50e8d34773da556210ad34d6157763">abs<int></a>(<span class="keywordtype">int</span> x) { <a class="code" href="group__metric__grp.html#gaf15608f8914516f8d949a8c053d55021">return ::abs</a>(x); }
<a name="l00216"></a><a class="code" href="group__metric__grp.html#ga3c252a1b86662381fd025b0576124c2d">00216</a> <span class="keyword">template</span><> <span class="keyword">inline</span> <span class="keywordtype">float</span> <a class="code" href="group__metric__grp.html#ga3c252a1b86662381fd025b0576124c2d">abs<float></a>(<span class="keywordtype">float</span> x) { <span class="keywordflow">return</span> fabsf(x); }
<a name="l00217"></a><a class="code" href="group__metric__grp.html#ga3fb0513e5af33647f17713a36b10f156">00217</a> <span class="keyword">template</span><> <span class="keyword">inline</span> <span class="keywordtype">double</span> <a class="code" href="group__metric__grp.html#ga3fb0513e5af33647f17713a36b10f156">abs<double></a>(<span class="keywordtype">double</span> x) { <span class="keywordflow">return</span> fabs(x); }
<a name="l00218"></a><a class="code" href="group__metric__grp.html#ga02cfdf1bf211628b049ffd239a26e57e">00218</a> <span class="keyword">template</span><> <span class="keyword">inline</span> <span class="keywordtype">long</span> <span class="keywordtype">double</span> <a class="code" href="group__metric__grp.html#ga02cfdf1bf211628b049ffd239a26e57e">abs<long double></a>(<span class="keywordtype">long</span> <span class="keywordtype">double</span> x) { <span class="keywordflow">return</span> fabsl(x); }
<a name="l00219"></a>00219 <span class="comment"></span>
<a name="l00220"></a>00220 <span class="comment"> /** Manhattan distance functor (generic version, optimized for high-dimensionality data sets).</span>
<a name="l00221"></a>00221 <span class="comment"> * Corresponding distance traits: nanoflann::metric_L1</span>
<a name="l00222"></a>00222 <span class="comment"> */</span>
<a name="l00223"></a>00223 <span class="keyword">template</span><<span class="keyword">class</span> T, <span class="keyword">class</span> DataSource>
<a name="l00224"></a>00224 <span class="keyword">struct </span>L1_Adaptor
<a name="l00225"></a>00225 {
<a name="l00226"></a><a class="code" href="structnanoflann_1_1_l1___adaptor.html#a1a9cdf7fdd795eb12646b5cb145004cd">00226</a> <span class="keyword">typedef</span> T <a class="code" href="structnanoflann_1_1_l1___adaptor.html#a1a9cdf7fdd795eb12646b5cb145004cd">ElementType</a>;
<a name="l00227"></a><a class="code" href="structnanoflann_1_1_l1___adaptor.html#a8f8d4a4824fb447455f77909c6f3e353">00227</a> <span class="keyword">typedef</span> T <a class="code" href="structnanoflann_1_1_l1___adaptor.html#a8f8d4a4824fb447455f77909c6f3e353">DistanceType</a>;
<a name="l00228"></a><a class="code" href="structnanoflann_1_1_l1___adaptor.html#a85ab3392c94cdeea62af0a9e980aecce">00228</a> <span class="keyword">typedef</span> T <a class="code" href="structnanoflann_1_1_l1___adaptor.html#a85ab3392c94cdeea62af0a9e980aecce">ResultType</a>;
<a name="l00229"></a>00229
<a name="l00230"></a><a class="code" href="structnanoflann_1_1_l1___adaptor.html#ab5148099d76235b3f83ed99c165536e8">00230</a> <span class="keyword">const</span> DataSource &<a class="code" href="structnanoflann_1_1_l1___adaptor.html#ab5148099d76235b3f83ed99c165536e8">data_source</a>;
<a name="l00231"></a>00231
<a name="l00232"></a><a class="code" href="structnanoflann_1_1_l1___adaptor.html#a08d4390bc31b0ece43e20183d1a96f28">00232</a> <a class="code" href="structnanoflann_1_1_l1___adaptor.html#a08d4390bc31b0ece43e20183d1a96f28">L1_Adaptor</a>(<span class="keyword">const</span> DataSource &_data_source) : data_source(_data_source) { }
<a name="l00233"></a>00233
<a name="l00234"></a><a class="code" href="structnanoflann_1_1_l1___adaptor.html#ac50a8ead3f0c25d23f292aedb271b082">00234</a> <span class="keyword">inline</span> T operator()(<span class="keyword">const</span> T* a, <span class="keyword">const</span> <span class="keywordtype">size_t</span> b_idx, <span class="keywordtype">size_t</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a1ccd37d4307264f3c70abb55dc5d57e1">size</a>, <a class="code" href="structnanoflann_1_1_l1___adaptor.html#a85ab3392c94cdeea62af0a9e980aecce">ResultType</a> worst_dist = -1)<span class="keyword"> const</span>
<a name="l00235"></a>00235 <span class="keyword"> </span>{
<a name="l00236"></a>00236 <a class="code" href="structnanoflann_1_1_l1___adaptor.html#a85ab3392c94cdeea62af0a9e980aecce">ResultType</a> result = <a class="code" href="structnanoflann_1_1_l1___adaptor.html#a85ab3392c94cdeea62af0a9e980aecce">ResultType</a>();
<a name="l00237"></a>00237 <span class="keyword">const</span> T* last = a + <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a1ccd37d4307264f3c70abb55dc5d57e1">size</a>;
<a name="l00238"></a>00238 <span class="keyword">const</span> T* lastgroup = last - 3;
<a name="l00239"></a>00239 <span class="keywordtype">size_t</span> d = 0;
<a name="l00240"></a>00240
<a name="l00241"></a>00241 <span class="comment">/* Process 4 items with each loop for efficiency. */</span>
<a name="l00242"></a>00242 <span class="keywordflow">while</span> (a < lastgroup) {
<a name="l00243"></a>00243 <span class="keyword">const</span> <a class="code" href="structnanoflann_1_1_l1___adaptor.html#a85ab3392c94cdeea62af0a9e980aecce">ResultType</a> diff0 = <a class="code" href="group__metric__grp.html#gaf15608f8914516f8d949a8c053d55021">nanoflann::abs</a>(a[0] - data_source.kdtree_get_pt(b_idx,d++));
<a name="l00244"></a>00244 <span class="keyword">const</span> <a class="code" href="structnanoflann_1_1_l1___adaptor.html#a85ab3392c94cdeea62af0a9e980aecce">ResultType</a> diff1 = <a class="code" href="group__metric__grp.html#gaf15608f8914516f8d949a8c053d55021">nanoflann::abs</a>(a[1] - data_source.kdtree_get_pt(b_idx,d++));
<a name="l00245"></a>00245 <span class="keyword">const</span> <a class="code" href="structnanoflann_1_1_l1___adaptor.html#a85ab3392c94cdeea62af0a9e980aecce">ResultType</a> diff2 = <a class="code" href="group__metric__grp.html#gaf15608f8914516f8d949a8c053d55021">nanoflann::abs</a>(a[2] - data_source.kdtree_get_pt(b_idx,d++));
<a name="l00246"></a>00246 <span class="keyword">const</span> <a class="code" href="structnanoflann_1_1_l1___adaptor.html#a85ab3392c94cdeea62af0a9e980aecce">ResultType</a> diff3 = <a class="code" href="group__metric__grp.html#gaf15608f8914516f8d949a8c053d55021">nanoflann::abs</a>(a[3] - data_source.kdtree_get_pt(b_idx,d++));
<a name="l00247"></a>00247 result += diff0 + diff1 + diff2 + diff3;
<a name="l00248"></a>00248 a += 4;
<a name="l00249"></a>00249 <span class="keywordflow">if</span> ((worst_dist>0)&&(result>worst_dist)) {
<a name="l00250"></a>00250 <span class="keywordflow">return</span> result;
<a name="l00251"></a>00251 }
<a name="l00252"></a>00252 }
<a name="l00253"></a>00253 <span class="comment">/* Process last 0-3 components. Not needed for standard vector lengths. */</span>
<a name="l00254"></a>00254 <span class="keywordflow">while</span> (a < last) {
<a name="l00255"></a>00255 result += <a class="code" href="group__metric__grp.html#gaf15608f8914516f8d949a8c053d55021">nanoflann::abs</a>( *a++ - data_source.kdtree_get_pt(b_idx,d++) );
<a name="l00256"></a>00256 }
<a name="l00257"></a>00257 <span class="keywordflow">return</span> result;
<a name="l00258"></a>00258 }
<a name="l00259"></a>00259
<a name="l00260"></a>00260 <span class="keyword">template</span> <<span class="keyword">typename</span> U, <span class="keyword">typename</span> V>
<a name="l00261"></a><a class="code" href="structnanoflann_1_1_l1___adaptor.html#a857490c4113e96e17e0ad77383be45aa">00261</a> <span class="keyword">inline</span> T accum_dist(<span class="keyword">const</span> U a, <span class="keyword">const</span> V b, <span class="keywordtype">int</span> dim)<span class="keyword"> const</span>
<a name="l00262"></a>00262 <span class="keyword"> </span>{
<a name="l00263"></a>00263 <span class="keywordflow">return</span> (a-b)*(a-b);
<a name="l00264"></a>00264 }
<a name="l00265"></a>00265 };
<a name="l00266"></a>00266 <span class="comment"></span>
<a name="l00267"></a>00267 <span class="comment"> /** Squared Euclidean distance functor (generic version, optimized for high-dimensionality data sets).</span>
<a name="l00268"></a>00268 <span class="comment"> * Corresponding distance traits: nanoflann::metric_L2</span>
<a name="l00269"></a>00269 <span class="comment"> */</span>
<a name="l00270"></a>00270 <span class="keyword">template</span><<span class="keyword">class</span> T, <span class="keyword">class</span> DataSource>
<a name="l00271"></a>00271 <span class="keyword">struct </span>L2_Adaptor
<a name="l00272"></a>00272 {
<a name="l00273"></a><a class="code" href="structnanoflann_1_1_l2___adaptor.html#a931731a0e2275b8043b57bcb35fc0bfa">00273</a> <span class="keyword">typedef</span> T <a class="code" href="structnanoflann_1_1_l2___adaptor.html#a931731a0e2275b8043b57bcb35fc0bfa">ElementType</a>;
<a name="l00274"></a><a class="code" href="structnanoflann_1_1_l2___adaptor.html#a8dee60d89d610a77788a9fa69bdeb118">00274</a> <span class="keyword">typedef</span> T <a class="code" href="structnanoflann_1_1_l2___adaptor.html#a8dee60d89d610a77788a9fa69bdeb118">DistanceType</a>;
<a name="l00275"></a><a class="code" href="structnanoflann_1_1_l2___adaptor.html#aa4175db1d490fe3a8ee26cd1fb4d187a">00275</a> <span class="keyword">typedef</span> T <a class="code" href="structnanoflann_1_1_l2___adaptor.html#aa4175db1d490fe3a8ee26cd1fb4d187a">ResultType</a>;
<a name="l00276"></a>00276
<a name="l00277"></a><a class="code" href="structnanoflann_1_1_l2___adaptor.html#a00bb0389ad6c78d01ff37b5852986205">00277</a> <span class="keyword">const</span> DataSource &<a class="code" href="structnanoflann_1_1_l2___adaptor.html#a00bb0389ad6c78d01ff37b5852986205">data_source</a>;
<a name="l00278"></a>00278
<a name="l00279"></a><a class="code" href="structnanoflann_1_1_l2___adaptor.html#a89cd19f4d22f691ebcb57bbb121eb752">00279</a> <a class="code" href="structnanoflann_1_1_l2___adaptor.html#a89cd19f4d22f691ebcb57bbb121eb752">L2_Adaptor</a>(<span class="keyword">const</span> DataSource &_data_source) : data_source(_data_source) { }
<a name="l00280"></a>00280
<a name="l00281"></a><a class="code" href="structnanoflann_1_1_l2___adaptor.html#af464f294ac85d7374b64263bb335586c">00281</a> <span class="keyword">inline</span> T operator()(<span class="keyword">const</span> T* a, <span class="keyword">const</span> <span class="keywordtype">size_t</span> b_idx, <span class="keywordtype">size_t</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a1ccd37d4307264f3c70abb55dc5d57e1">size</a>, <a class="code" href="structnanoflann_1_1_l2___adaptor.html#aa4175db1d490fe3a8ee26cd1fb4d187a">ResultType</a> worst_dist = -1)<span class="keyword"> const</span>
<a name="l00282"></a>00282 <span class="keyword"> </span>{
<a name="l00283"></a>00283 <a class="code" href="structnanoflann_1_1_l2___adaptor.html#aa4175db1d490fe3a8ee26cd1fb4d187a">ResultType</a> result = <a class="code" href="structnanoflann_1_1_l2___adaptor.html#aa4175db1d490fe3a8ee26cd1fb4d187a">ResultType</a>();
<a name="l00284"></a>00284 <span class="keyword">const</span> T* last = a + <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a1ccd37d4307264f3c70abb55dc5d57e1">size</a>;
<a name="l00285"></a>00285 <span class="keyword">const</span> T* lastgroup = last - 3;
<a name="l00286"></a>00286 <span class="keywordtype">size_t</span> d = 0;
<a name="l00287"></a>00287
<a name="l00288"></a>00288 <span class="comment">/* Process 4 items with each loop for efficiency. */</span>
<a name="l00289"></a>00289 <span class="keywordflow">while</span> (a < lastgroup) {
<a name="l00290"></a>00290 <span class="keyword">const</span> <a class="code" href="structnanoflann_1_1_l2___adaptor.html#aa4175db1d490fe3a8ee26cd1fb4d187a">ResultType</a> diff0 = a[0] - data_source.kdtree_get_pt(b_idx,d++);
<a name="l00291"></a>00291 <span class="keyword">const</span> <a class="code" href="structnanoflann_1_1_l2___adaptor.html#aa4175db1d490fe3a8ee26cd1fb4d187a">ResultType</a> diff1 = a[1] - data_source.kdtree_get_pt(b_idx,d++);
<a name="l00292"></a>00292 <span class="keyword">const</span> <a class="code" href="structnanoflann_1_1_l2___adaptor.html#aa4175db1d490fe3a8ee26cd1fb4d187a">ResultType</a> diff2 = a[2] - data_source.kdtree_get_pt(b_idx,d++);
<a name="l00293"></a>00293 <span class="keyword">const</span> <a class="code" href="structnanoflann_1_1_l2___adaptor.html#aa4175db1d490fe3a8ee26cd1fb4d187a">ResultType</a> diff3 = a[3] - data_source.kdtree_get_pt(b_idx,d++);
<a name="l00294"></a>00294 result += diff0 * diff0 + diff1 * diff1 + diff2 * diff2 + diff3 * diff3;
<a name="l00295"></a>00295 a += 4;
<a name="l00296"></a>00296 <span class="keywordflow">if</span> ((worst_dist>0)&&(result>worst_dist)) {
<a name="l00297"></a>00297 <span class="keywordflow">return</span> result;
<a name="l00298"></a>00298 }
<a name="l00299"></a>00299 }
<a name="l00300"></a>00300 <span class="comment">/* Process last 0-3 components. Not needed for standard vector lengths. */</span>
<a name="l00301"></a>00301 <span class="keywordflow">while</span> (a < last) {
<a name="l00302"></a>00302 <span class="keyword">const</span> <a class="code" href="structnanoflann_1_1_l2___adaptor.html#aa4175db1d490fe3a8ee26cd1fb4d187a">ResultType</a> diff0 = *a++ - data_source.kdtree_get_pt(b_idx,d++);
<a name="l00303"></a>00303 result += diff0 * diff0;
<a name="l00304"></a>00304 }
<a name="l00305"></a>00305 <span class="keywordflow">return</span> result;
<a name="l00306"></a>00306 }
<a name="l00307"></a>00307
<a name="l00308"></a>00308 <span class="keyword">template</span> <<span class="keyword">typename</span> U, <span class="keyword">typename</span> V>
<a name="l00309"></a><a class="code" href="structnanoflann_1_1_l2___adaptor.html#a702954337a72f398050eab16f3e70e03">00309</a> <span class="keyword">inline</span> T accum_dist(<span class="keyword">const</span> U a, <span class="keyword">const</span> V b, <span class="keywordtype">int</span> dim)<span class="keyword"> const</span>
<a name="l00310"></a>00310 <span class="keyword"> </span>{
<a name="l00311"></a>00311 <span class="keywordflow">return</span> (a-b)*(a-b);
<a name="l00312"></a>00312 }
<a name="l00313"></a>00313 };
<a name="l00314"></a>00314 <span class="comment"></span>
<a name="l00315"></a>00315 <span class="comment"> /** Squared Euclidean distance functor (suitable for low-dimensionality datasets, like 2D or 3D point clouds)</span>
<a name="l00316"></a>00316 <span class="comment"> * Corresponding distance traits: nanoflann::metric_L2_Simple</span>
<a name="l00317"></a>00317 <span class="comment"> */</span>
<a name="l00318"></a>00318 <span class="keyword">template</span><<span class="keyword">class</span> T, <span class="keyword">class</span> DataSource>
<a name="l00319"></a>00319 <span class="keyword">struct </span>L2_Simple_Adaptor
<a name="l00320"></a>00320 {
<a name="l00321"></a><a class="code" href="structnanoflann_1_1_l2___simple___adaptor.html#a69706a9c30878ce28800158e77b927a8">00321</a> <span class="keyword">typedef</span> T <a class="code" href="structnanoflann_1_1_l2___simple___adaptor.html#a69706a9c30878ce28800158e77b927a8">ElementType</a>;
<a name="l00322"></a><a class="code" href="structnanoflann_1_1_l2___simple___adaptor.html#aad89d039f33f671f4616581663b0291f">00322</a> <span class="keyword">typedef</span> T <a class="code" href="structnanoflann_1_1_l2___simple___adaptor.html#aad89d039f33f671f4616581663b0291f">DistanceType</a>;
<a name="l00323"></a><a class="code" href="structnanoflann_1_1_l2___simple___adaptor.html#ad3ddb6080e052b19c74579e19517cfd3">00323</a> <span class="keyword">typedef</span> T <a class="code" href="structnanoflann_1_1_l2___simple___adaptor.html#ad3ddb6080e052b19c74579e19517cfd3">ResultType</a>;
<a name="l00324"></a>00324
<a name="l00325"></a><a class="code" href="structnanoflann_1_1_l2___simple___adaptor.html#a6b815fda5713a7298ea7fac21f732c59">00325</a> <span class="keyword">const</span> DataSource &<a class="code" href="structnanoflann_1_1_l2___simple___adaptor.html#a6b815fda5713a7298ea7fac21f732c59">data_source</a>;
<a name="l00326"></a>00326
<a name="l00327"></a><a class="code" href="structnanoflann_1_1_l2___simple___adaptor.html#ab6bc07039cc3ab4831ba59d31f017c61">00327</a> <a class="code" href="structnanoflann_1_1_l2___simple___adaptor.html#ab6bc07039cc3ab4831ba59d31f017c61">L2_Simple_Adaptor</a>(<span class="keyword">const</span> DataSource &_data_source) : data_source(_data_source) { }
<a name="l00328"></a>00328
<a name="l00329"></a><a class="code" href="structnanoflann_1_1_l2___simple___adaptor.html#af7042692a6a650f4e294067b68fa8407">00329</a> <span class="keyword">inline</span> T <a class="code" href="structnanoflann_1_1_l2___simple___adaptor.html#af7042692a6a650f4e294067b68fa8407">operator()</a>(<span class="keyword">const</span> T* a, <span class="keyword">const</span> <span class="keywordtype">size_t</span> b_idx, <span class="keywordtype">size_t</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a1ccd37d4307264f3c70abb55dc5d57e1">size</a>)<span class="keyword"> const </span>{
<a name="l00330"></a>00330 <span class="keywordflow">return</span> data_source.kdtree_distance(a,b_idx,size);
<a name="l00331"></a>00331 }
<a name="l00332"></a>00332
<a name="l00333"></a>00333 <span class="keyword">template</span> <<span class="keyword">typename</span> U, <span class="keyword">typename</span> V>
<a name="l00334"></a><a class="code" href="structnanoflann_1_1_l2___simple___adaptor.html#a7842ad4698cfb74239931021bd98db6d">00334</a> <span class="keyword">inline</span> T accum_dist(<span class="keyword">const</span> U a, <span class="keyword">const</span> V b, <span class="keywordtype">int</span> dim)<span class="keyword"> const</span>
<a name="l00335"></a>00335 <span class="keyword"> </span>{
<a name="l00336"></a>00336 <span class="keywordflow">return</span> (a-b)*(a-b);
<a name="l00337"></a>00337 }
<a name="l00338"></a>00338 };
<a name="l00339"></a>00339 <span class="comment"></span>
<a name="l00340"></a>00340 <span class="comment"> /** Metaprogramming helper traits class for the L1 (Manhattan) metric */</span>
<a name="l00341"></a>00341 <span class="keyword">struct </span>metric_L1 {
<a name="l00342"></a>00342 <span class="keyword">template</span><<span class="keyword">class</span> T, <span class="keyword">class</span> DataSource>
<a name="l00343"></a>00343 <span class="keyword">struct </span>traits {
<a name="l00344"></a><a class="code" href="structnanoflann_1_1metric___l1_1_1traits.html#a64779c887784aaab1bdd2d431b150b0c">00344</a> <span class="keyword">typedef</span> <a class="code" href="structnanoflann_1_1_l1___adaptor.html" title="Manhattan distance functor (generic version, optimized for high-dimensionality data sets)...">L1_Adaptor<T,DataSource></a> <a class="code" href="structnanoflann_1_1metric___l1_1_1traits.html#a64779c887784aaab1bdd2d431b150b0c">distance_t</a>;
<a name="l00345"></a>00345 };
<a name="l00346"></a>00346 };<span class="comment"></span>
<a name="l00347"></a>00347 <span class="comment"> /** Metaprogramming helper traits class for the L2 (Euclidean) metric */</span>
<a name="l00348"></a>00348 <span class="keyword">struct </span><a class="code" href="structnanoflann_1_1metric___l2.html" title="Metaprogramming helper traits class for the L2 (Euclidean) metric.">metric_L2</a> {
<a name="l00349"></a>00349 <span class="keyword">template</span><<span class="keyword">class</span> T, <span class="keyword">class</span> DataSource>
<a name="l00350"></a>00350 <span class="keyword">struct </span>traits {
<a name="l00351"></a><a class="code" href="structnanoflann_1_1metric___l2_1_1traits.html#abce11e8a1ec5b7dabb56352c9657d666">00351</a> <span class="keyword">typedef</span> <a class="code" href="structnanoflann_1_1_l2___adaptor.html" title="Squared Euclidean distance functor (generic version, optimized for high-dimensionality data sets)...">L2_Adaptor<T,DataSource></a> <a class="code" href="structnanoflann_1_1metric___l2_1_1traits.html#abce11e8a1ec5b7dabb56352c9657d666">distance_t</a>;
<a name="l00352"></a>00352 };
<a name="l00353"></a>00353 };<span class="comment"></span>
<a name="l00354"></a>00354 <span class="comment"> /** Metaprogramming helper traits class for the L2_simple (Euclidean) metric */</span>
<a name="l00355"></a>00355 <span class="keyword">struct </span><a class="code" href="structnanoflann_1_1metric___l2___simple.html" title="Metaprogramming helper traits class for the L2_simple (Euclidean) metric.">metric_L2_Simple</a> {
<a name="l00356"></a>00356 <span class="keyword">template</span><<span class="keyword">class</span> T, <span class="keyword">class</span> DataSource>
<a name="l00357"></a>00357 <span class="keyword">struct </span>traits {
<a name="l00358"></a><a class="code" href="structnanoflann_1_1metric___l2___simple_1_1traits.html#a420b8efc804e5c8d070b5df028a3cb33">00358</a> <span class="keyword">typedef</span> <a class="code" href="structnanoflann_1_1_l2___simple___adaptor.html" title="Squared Euclidean distance functor (suitable for low-dimensionality datasets, like 2D or 3D point clo...">L2_Simple_Adaptor<T,DataSource></a> <a class="code" href="structnanoflann_1_1metric___l2___simple_1_1traits.html#a420b8efc804e5c8d070b5df028a3cb33">distance_t</a>;
<a name="l00359"></a>00359 };
<a name="l00360"></a>00360 };
<a name="l00361"></a>00361 <span class="comment"></span>
<a name="l00362"></a>00362 <span class="comment"> /** @} */</span>
<a name="l00363"></a>00363
<a name="l00364"></a>00364
<a name="l00365"></a>00365 <span class="comment"></span>
<a name="l00366"></a>00366 <span class="comment"> /** @addtogroup param_grp Parameter structs</span>
<a name="l00367"></a>00367 <span class="comment"> * @{ */</span>
<a name="l00368"></a>00368 <span class="comment"></span>
<a name="l00369"></a>00369 <span class="comment"> /** Parameters</span>
<a name="l00370"></a>00370 <span class="comment"> */</span>
<a name="l00371"></a>00371 <span class="keyword">struct </span><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_params.html" title="Parameters.">KDTreeSingleIndexAdaptorParams</a>
<a name="l00372"></a>00372 {
<a name="l00373"></a><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_params.html#a106f9b214a89bf0516cd4b927941c8b2">00373</a> <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_params.html" title="Parameters.">KDTreeSingleIndexAdaptorParams</a>(<span class="keywordtype">int</span> leaf_max_size_ = 10, <span class="keywordtype">int</span> dim_ = -1) :
<a name="l00374"></a>00374 leaf_max_size(leaf_max_size_), dim(dim_)
<a name="l00375"></a>00375 {}
<a name="l00376"></a>00376
<a name="l00377"></a><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_params.html#a26dc54c1586a14f4c49f6bf5431d8ae3">00377</a> <span class="keywordtype">int</span> <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_params.html#a26dc54c1586a14f4c49f6bf5431d8ae3">leaf_max_size</a>;
<a name="l00378"></a><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_params.html#a3fa490f233559594e34b3c1fcb8e5057">00378</a> <span class="keywordtype">int</span> <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_params.html#a3fa490f233559594e34b3c1fcb8e5057">dim</a>;
<a name="l00379"></a>00379 };
<a name="l00380"></a>00380 <span class="comment"></span>
<a name="l00381"></a>00381 <span class="comment"> /** Search options for KDTreeSingleIndexAdaptor::findNeighbors() */</span>
<a name="l00382"></a>00382 <span class="keyword">struct </span><a class="code" href="structnanoflann_1_1_search_params.html" title="Search options for KDTreeSingleIndexAdaptor::findNeighbors()">SearchParams</a>
<a name="l00383"></a>00383 {
<a name="l00384"></a><a class="code" href="structnanoflann_1_1_search_params.html#a927db6b31a7ec66d0e4d9dc62c482f34">00384</a> <a class="code" href="structnanoflann_1_1_search_params.html" title="Search options for KDTreeSingleIndexAdaptor::findNeighbors()">SearchParams</a>(<span class="keywordtype">int</span> checks_ = 32, <span class="keywordtype">float</span> eps_ = 0, <span class="keywordtype">bool</span> sorted_ = <span class="keyword">true</span> ) :
<a name="l00385"></a>00385 checks(checks_), eps(eps_), sorted(sorted_) {}
<a name="l00386"></a>00386
<a name="l00387"></a><a class="code" href="structnanoflann_1_1_search_params.html#a904f56b474fb6ff0aaa632e9329d9dda">00387</a> <span class="keywordtype">int</span> <a class="code" href="structnanoflann_1_1_search_params.html#a904f56b474fb6ff0aaa632e9329d9dda" title="how many leafs to visit when searching for neighbours (-1 for unlimited)">checks</a>; <span class="comment">//!< how many leafs to visit when searching for neighbours (-1 for unlimited)</span>
<a name="l00388"></a><a class="code" href="structnanoflann_1_1_search_params.html#a64b9e7c56bbb743694f6188f616a94cc">00388</a> <span class="comment"></span> <span class="keywordtype">float</span> <a class="code" href="structnanoflann_1_1_search_params.html#a64b9e7c56bbb743694f6188f616a94cc" title="search for eps-approximate neighbours (default: 0)">eps</a>; <span class="comment">//!< search for eps-approximate neighbours (default: 0)</span>
<a name="l00389"></a><a class="code" href="structnanoflann_1_1_search_params.html#a5126d5f71f1c9163c6a581776a0e9466">00389</a> <span class="comment"></span> <span class="keywordtype">bool</span> <a class="code" href="structnanoflann_1_1_search_params.html#a5126d5f71f1c9163c6a581776a0e9466" title="only for radius search, require neighbours sorted by distance (default: true)">sorted</a>; <span class="comment">//!< only for radius search, require neighbours sorted by distance (default: true)</span>
<a name="l00390"></a>00390 <span class="comment"></span> };<span class="comment"></span>
<a name="l00391"></a>00391 <span class="comment"> /** @} */</span>
<a name="l00392"></a>00392
<a name="l00393"></a>00393 <span class="comment"></span>
<a name="l00394"></a>00394 <span class="comment"> /** @addtogroup memalloc_grp Memory allocation</span>
<a name="l00395"></a>00395 <span class="comment"> * @{ */</span>
<a name="l00396"></a>00396 <span class="comment"></span>
<a name="l00397"></a>00397 <span class="comment"> /**</span>
<a name="l00398"></a>00398 <span class="comment"> * Allocates (using C's malloc) a generic type T.</span>
<a name="l00399"></a>00399 <span class="comment"> *</span>
<a name="l00400"></a>00400 <span class="comment"> * Params:</span>
<a name="l00401"></a>00401 <span class="comment"> * count = number of instances to allocate.</span>
<a name="l00402"></a>00402 <span class="comment"> * Returns: pointer (of type T*) to memory buffer</span>
<a name="l00403"></a>00403 <span class="comment"> */</span>
<a name="l00404"></a>00404 <span class="keyword">template</span> <<span class="keyword">typename</span> T>
<a name="l00405"></a><a class="code" href="group__memalloc__grp.html#ga477667da2a8edb1d65f5a7eebaffc1eb">00405</a> T* <a class="code" href="group__memalloc__grp.html#ga477667da2a8edb1d65f5a7eebaffc1eb" title="Allocates (using C's malloc) a generic type T.">allocate</a>(<span class="keywordtype">size_t</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">count</a> = 1)
<a name="l00406"></a>00406 {
<a name="l00407"></a>00407 T* mem = (T*) ::malloc(<span class="keyword">sizeof</span>(T)*<a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">count</a>);
<a name="l00408"></a>00408 <span class="keywordflow">return</span> mem;
<a name="l00409"></a>00409 }
<a name="l00410"></a>00410
<a name="l00411"></a>00411 <span class="comment"></span>
<a name="l00412"></a>00412 <span class="comment"> /**</span>
<a name="l00413"></a>00413 <span class="comment"> * Pooled storage allocator</span>
<a name="l00414"></a>00414 <span class="comment"> *</span>
<a name="l00415"></a>00415 <span class="comment"> * The following routines allow for the efficient allocation of storage in</span>
<a name="l00416"></a>00416 <span class="comment"> * small chunks from a specified pool. Rather than allowing each structure</span>
<a name="l00417"></a>00417 <span class="comment"> * to be freed individually, an entire pool of storage is freed at once.</span>
<a name="l00418"></a>00418 <span class="comment"> * This method has two advantages over just using malloc() and free(). First,</span>
<a name="l00419"></a>00419 <span class="comment"> * it is far more efficient for allocating small objects, as there is</span>
<a name="l00420"></a>00420 <span class="comment"> * no overhead for remembering all the information needed to free each</span>
<a name="l00421"></a>00421 <span class="comment"> * object or consolidating fragmented memory. Second, the decision about</span>
<a name="l00422"></a>00422 <span class="comment"> * how long to keep an object is made at the time of allocation, and there</span>
<a name="l00423"></a>00423 <span class="comment"> * is no need to track down all the objects to free them.</span>
<a name="l00424"></a>00424 <span class="comment"> *</span>
<a name="l00425"></a>00425 <span class="comment"> */</span>
<a name="l00426"></a>00426
<a name="l00427"></a><a class="code" href="group__memalloc__grp.html#ga40956ef8f797399b4f478df9fc1566f4">00427</a> <span class="keyword">const</span> <span class="keywordtype">size_t</span> <a class="code" href="group__memalloc__grp.html#ga40956ef8f797399b4f478df9fc1566f4" title="Pooled storage allocator.">WORDSIZE</a>=16;
<a name="l00428"></a><a class="code" href="group__memalloc__grp.html#gaf4df087b6f47e514f6062f7ada2d19d7">00428</a> <span class="keyword">const</span> <span class="keywordtype">size_t</span> <a class="code" href="group__memalloc__grp.html#gaf4df087b6f47e514f6062f7ada2d19d7">BLOCKSIZE</a>=8192;
<a name="l00429"></a>00429
<a name="l00430"></a>00430 <span class="keyword">class </span><a class="code" href="classnanoflann_1_1_pooled_allocator.html">PooledAllocator</a>
<a name="l00431"></a>00431 {
<a name="l00432"></a>00432 <span class="comment">/* We maintain memory alignment to word boundaries by requiring that all</span>
<a name="l00433"></a>00433 <span class="comment"> allocations be in multiples of the machine wordsize. */</span>
<a name="l00434"></a>00434 <span class="comment">/* Size of machine word in bytes. Must be power of 2. */</span>
<a name="l00435"></a>00435 <span class="comment">/* Minimum number of bytes requested at a time from the system. Must be multiple of WORDSIZE. */</span>
<a name="l00436"></a>00436
<a name="l00437"></a>00437
<a name="l00438"></a><a class="code" href="classnanoflann_1_1_pooled_allocator.html#a71aea2ea7ec8d97a1c2b02f11e99abf6">00438</a> <span class="keywordtype">int</span> <a class="code" href="classnanoflann_1_1_pooled_allocator.html#a71aea2ea7ec8d97a1c2b02f11e99abf6">remaining</a>; <span class="comment">/* Number of bytes left in current block of storage. */</span>
<a name="l00439"></a><a class="code" href="classnanoflann_1_1_pooled_allocator.html#a1148d8f26ecad3895b6740bd6a9cd4bc">00439</a> <span class="keywordtype">void</span>* <a class="code" href="classnanoflann_1_1_pooled_allocator.html#a1148d8f26ecad3895b6740bd6a9cd4bc">base</a>; <span class="comment">/* Pointer to base of current block of storage. */</span>
<a name="l00440"></a><a class="code" href="classnanoflann_1_1_pooled_allocator.html#acf372c9c0847b39e61157e9e071e64b5">00440</a> <span class="keywordtype">void</span>* <a class="code" href="classnanoflann_1_1_pooled_allocator.html#acf372c9c0847b39e61157e9e071e64b5">loc</a>; <span class="comment">/* Current location in block to next allocate memory. */</span>
<a name="l00441"></a><a class="code" href="classnanoflann_1_1_pooled_allocator.html#aed8adaf0d8cc9e62da6d01a97fc81e94">00441</a> <span class="keywordtype">int</span> <a class="code" href="classnanoflann_1_1_pooled_allocator.html#aed8adaf0d8cc9e62da6d01a97fc81e94">blocksize</a>;
<a name="l00442"></a>00442
<a name="l00443"></a>00443
<a name="l00444"></a>00444 <span class="keyword">public</span>:
<a name="l00445"></a><a class="code" href="classnanoflann_1_1_pooled_allocator.html#a55b826895bc21e996b89da4cf90d5b6d">00445</a> <span class="keywordtype">int</span> <a class="code" href="classnanoflann_1_1_pooled_allocator.html#a55b826895bc21e996b89da4cf90d5b6d">usedMemory</a>;
<a name="l00446"></a><a class="code" href="classnanoflann_1_1_pooled_allocator.html#aa9e6ae36fe30290763fc359915a359fb">00446</a> <span class="keywordtype">int</span> <a class="code" href="classnanoflann_1_1_pooled_allocator.html#aa9e6ae36fe30290763fc359915a359fb">wastedMemory</a>;
<a name="l00447"></a>00447 <span class="comment"></span>
<a name="l00448"></a>00448 <span class="comment"> /**</span>
<a name="l00449"></a>00449 <span class="comment"> Default constructor. Initializes a new pool.</span>
<a name="l00450"></a>00450 <span class="comment"> */</span>
<a name="l00451"></a><a class="code" href="classnanoflann_1_1_pooled_allocator.html#a455bad91ea68e09185d49bd6713e0e41">00451</a> <a class="code" href="classnanoflann_1_1_pooled_allocator.html">PooledAllocator</a>(<span class="keywordtype">int</span> blocksize = <a class="code" href="group__memalloc__grp.html#gaf4df087b6f47e514f6062f7ada2d19d7">BLOCKSIZE</a>)
<a name="l00452"></a>00452 {
<a name="l00453"></a>00453 this->blocksize = blocksize;
<a name="l00454"></a>00454 remaining = 0;
<a name="l00455"></a>00455 base = NULL;
<a name="l00456"></a>00456
<a name="l00457"></a>00457 usedMemory = 0;
<a name="l00458"></a>00458 wastedMemory = 0;
<a name="l00459"></a>00459 }
<a name="l00460"></a>00460 <span class="comment"></span>
<a name="l00461"></a>00461 <span class="comment"> /**</span>
<a name="l00462"></a>00462 <span class="comment"> * Destructor. Frees all the memory allocated in this pool.</span>
<a name="l00463"></a>00463 <span class="comment"> */</span>
<a name="l00464"></a><a class="code" href="classnanoflann_1_1_pooled_allocator.html#a39c53213bc49d0f08fb8e4b0adc25b5e">00464</a> ~<a class="code" href="classnanoflann_1_1_pooled_allocator.html">PooledAllocator</a>()
<a name="l00465"></a>00465 {
<a name="l00466"></a>00466 <span class="keywordtype">void</span>* prev;
<a name="l00467"></a>00467
<a name="l00468"></a>00468 <span class="keywordflow">while</span> (base != NULL) {
<a name="l00469"></a>00469 prev = *((<span class="keywordtype">void</span>**) base); <span class="comment">/* Get pointer to prev block. */</span>
<a name="l00470"></a>00470 ::free(base);
<a name="l00471"></a>00471 base = prev;
<a name="l00472"></a>00472 }
<a name="l00473"></a>00473 }
<a name="l00474"></a>00474 <span class="comment"></span>
<a name="l00475"></a>00475 <span class="comment"> /**</span>
<a name="l00476"></a>00476 <span class="comment"> * Returns a pointer to a piece of new memory of the given size in bytes</span>
<a name="l00477"></a>00477 <span class="comment"> * allocated from the pool.</span>
<a name="l00478"></a>00478 <span class="comment"> */</span>
<a name="l00479"></a><a class="code" href="classnanoflann_1_1_pooled_allocator.html#a10bd3c4dc24afffcb8a9978a4146d936">00479</a> <span class="keywordtype">void</span>* malloc(<span class="keywordtype">int</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a1ccd37d4307264f3c70abb55dc5d57e1">size</a>)
<a name="l00480"></a>00480 {
<a name="l00481"></a>00481 <span class="keywordtype">int</span> blocksize;
<a name="l00482"></a>00482
<a name="l00483"></a>00483 <span class="comment">/* Round size up to a multiple of wordsize. The following expression</span>
<a name="l00484"></a>00484 <span class="comment"> only works for WORDSIZE that is a power of 2, by masking last bits of</span>
<a name="l00485"></a>00485 <span class="comment"> incremented size to zero.</span>
<a name="l00486"></a>00486 <span class="comment"> */</span>
<a name="l00487"></a>00487 size = (size + (<a class="code" href="group__memalloc__grp.html#ga40956ef8f797399b4f478df9fc1566f4" title="Pooled storage allocator.">WORDSIZE</a> - 1)) & ~(<a class="code" href="group__memalloc__grp.html#ga40956ef8f797399b4f478df9fc1566f4" title="Pooled storage allocator.">WORDSIZE</a> - 1);
<a name="l00488"></a>00488
<a name="l00489"></a>00489 <span class="comment">/* Check whether a new block must be allocated. Note that the first word</span>
<a name="l00490"></a>00490 <span class="comment"> of a block is reserved for a pointer to the previous block.</span>
<a name="l00491"></a>00491 <span class="comment"> */</span>
<a name="l00492"></a>00492 <span class="keywordflow">if</span> (size > remaining) {
<a name="l00493"></a>00493
<a name="l00494"></a>00494 wastedMemory += remaining;
<a name="l00495"></a>00495
<a name="l00496"></a>00496 <span class="comment">/* Allocate new storage. */</span>
<a name="l00497"></a>00497 blocksize = (size + <span class="keyword">sizeof</span>(<span class="keywordtype">void</span>*) + (<a class="code" href="group__memalloc__grp.html#ga40956ef8f797399b4f478df9fc1566f4" title="Pooled storage allocator.">WORDSIZE</a>-1) > <a class="code" href="group__memalloc__grp.html#gaf4df087b6f47e514f6062f7ada2d19d7">BLOCKSIZE</a>) ?
<a name="l00498"></a>00498 size + <span class="keyword">sizeof</span>(<span class="keywordtype">void</span>*) + (<a class="code" href="group__memalloc__grp.html#ga40956ef8f797399b4f478df9fc1566f4" title="Pooled storage allocator.">WORDSIZE</a>-1) : <a class="code" href="group__memalloc__grp.html#gaf4df087b6f47e514f6062f7ada2d19d7">BLOCKSIZE</a>;
<a name="l00499"></a>00499
<a name="l00500"></a>00500 <span class="comment">// use the standard C malloc to allocate memory</span>
<a name="l00501"></a>00501 <span class="keywordtype">void</span>* m = ::malloc(blocksize);
<a name="l00502"></a>00502 <span class="keywordflow">if</span> (!m) {
<a name="l00503"></a>00503 <a class="code" href="group__mrpt__system__os.html#ga4cc3a0ea9b292a90300224b00e1c8fac" title="An OS-independent version of fprintf.">fprintf</a>(stderr,<span class="stringliteral">"Failed to allocate memory.\n"</span>);
<a name="l00504"></a>00504 <span class="keywordflow">return</span> NULL;
<a name="l00505"></a>00505 }
<a name="l00506"></a>00506
<a name="l00507"></a>00507 <span class="comment">/* Fill first word of new block with pointer to previous block. */</span>
<a name="l00508"></a>00508 ((<span class="keywordtype">void</span>**) m)[0] = base;
<a name="l00509"></a>00509 base = m;
<a name="l00510"></a>00510
<a name="l00511"></a>00511 <span class="keywordtype">int</span> shift = 0;
<a name="l00512"></a>00512 <span class="comment">//int shift = (WORDSIZE - ( (((size_t)m) + sizeof(void*)) & (WORDSIZE-1))) & (WORDSIZE-1);</span>
<a name="l00513"></a>00513
<a name="l00514"></a>00514 remaining = blocksize - <span class="keyword">sizeof</span>(<span class="keywordtype">void</span>*) - shift;
<a name="l00515"></a>00515 loc = ((<span class="keywordtype">char</span>*)m + <span class="keyword">sizeof</span>(<span class="keywordtype">void</span>*) + shift);
<a name="l00516"></a>00516 }
<a name="l00517"></a>00517 <span class="keywordtype">void</span>* rloc = loc;
<a name="l00518"></a>00518 loc = (<span class="keywordtype">char</span>*)loc + size;
<a name="l00519"></a>00519 remaining -= <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a1ccd37d4307264f3c70abb55dc5d57e1">size</a>;
<a name="l00520"></a>00520
<a name="l00521"></a>00521 usedMemory += <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a1ccd37d4307264f3c70abb55dc5d57e1">size</a>;
<a name="l00522"></a>00522
<a name="l00523"></a>00523 <span class="keywordflow">return</span> rloc;
<a name="l00524"></a>00524 }
<a name="l00525"></a>00525 <span class="comment"></span>
<a name="l00526"></a>00526 <span class="comment"> /**</span>
<a name="l00527"></a>00527 <span class="comment"> * Allocates (using this pool) a generic type T.</span>
<a name="l00528"></a>00528 <span class="comment"> *</span>
<a name="l00529"></a>00529 <span class="comment"> * Params:</span>
<a name="l00530"></a>00530 <span class="comment"> * count = number of instances to allocate.</span>
<a name="l00531"></a>00531 <span class="comment"> * Returns: pointer (of type T*) to memory buffer</span>
<a name="l00532"></a>00532 <span class="comment"> */</span>
<a name="l00533"></a>00533 <span class="keyword">template</span> <<span class="keyword">typename</span> T>
<a name="l00534"></a><a class="code" href="classnanoflann_1_1_pooled_allocator.html#a22eba1bba230bb32378103ae4bffd94f">00534</a> T* <a class="code" href="group__memalloc__grp.html#ga477667da2a8edb1d65f5a7eebaffc1eb" title="Allocates (using C's malloc) a generic type T.">allocate</a>(<span class="keywordtype">size_t</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">count</a> = 1)
<a name="l00535"></a>00535 {
<a name="l00536"></a>00536 T* mem = (T*) this->malloc(static_cast<int>( <span class="keyword">sizeof</span>(T)*<a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">count</a> ));
<a name="l00537"></a>00537 <span class="keywordflow">return</span> mem;
<a name="l00538"></a>00538 }
<a name="l00539"></a>00539
<a name="l00540"></a>00540 };<span class="comment"></span>
<a name="l00541"></a>00541 <span class="comment"> /** @} */</span>
<a name="l00542"></a>00542
<a name="l00543"></a>00543 <span class="comment"></span>
<a name="l00544"></a>00544 <span class="comment"> /** @addtogroup kdtrees_grp KD-tree classes and adaptors</span>
<a name="l00545"></a>00545 <span class="comment"> * @{ */</span>
<a name="l00546"></a>00546 <span class="comment"></span>
<a name="l00547"></a>00547 <span class="comment"> /** kd-tree index</span>
<a name="l00548"></a>00548 <span class="comment"> *</span>
<a name="l00549"></a>00549 <span class="comment"> * Contains the k-d trees and other information for indexing a set of points</span>
<a name="l00550"></a>00550 <span class="comment"> * for nearest-neighbor matching.</span>
<a name="l00551"></a>00551 <span class="comment"> *</span>
<a name="l00552"></a>00552 <span class="comment"> * The class "DatasetAdaptor" must provide the following interface (can be non-virtual, inlined methods):</span>
<a name="l00553"></a>00553 <span class="comment"> *</span>
<a name="l00554"></a>00554 <span class="comment"> * \code</span>
<a name="l00555"></a>00555 <span class="comment"> * // Must return the number of data points</span>
<a name="l00556"></a>00556 <span class="comment"> * inline size_t kdtree_get_point_count() const { ... }</span>
<a name="l00557"></a>00557 <span class="comment"> *</span>
<a name="l00558"></a>00558 <span class="comment"> * // Must return the Euclidean (L2) distance between the vector "p1[0:size-1]" and the data point with index "idx_p2" stored in the class:</span>
<a name="l00559"></a>00559 <span class="comment"> * inline float kdtree_distance(const float *p1, const size_t idx_p2,size_t size) const { ... }</span>
<a name="l00560"></a>00560 <span class="comment"> *</span>
<a name="l00561"></a>00561 <span class="comment"> * // Must return the dim'th component of the idx'th point in the class:</span>
<a name="l00562"></a>00562 <span class="comment"> * inline num_t kdtree_get_pt(const size_t idx, int dim) const { ... }</span>
<a name="l00563"></a>00563 <span class="comment"> *</span>
<a name="l00564"></a>00564 <span class="comment"> * // Optional bounding-box computation: return false to default to a standard bbox computation loop.</span>
<a name="l00565"></a>00565 <span class="comment"> * // Return true if the BBOX was already computed by the class and returned in "bb" so it can be avoided to redo it again.</span>
<a name="l00566"></a>00566 <span class="comment"> * // Look at bb.size() to find out the expected dimensionality (e.g. 2 or 3 for point clouds)</span>
<a name="l00567"></a>00567 <span class="comment"> * template <class BBOX></span>
<a name="l00568"></a>00568 <span class="comment"> * bool kdtree_get_bbox(BBOX &bb) const</span>
<a name="l00569"></a>00569 <span class="comment"> * {</span>
<a name="l00570"></a>00570 <span class="comment"> * bb[0].low = ...; bb[0].high = ...; // 0th dimension limits</span>
<a name="l00571"></a>00571 <span class="comment"> * bb[1].low = ...; bb[1].high = ...; // 1st dimension limits</span>
<a name="l00572"></a>00572 <span class="comment"> * ...</span>
<a name="l00573"></a>00573 <span class="comment"> * return true;</span>
<a name="l00574"></a>00574 <span class="comment"> * }</span>
<a name="l00575"></a>00575 <span class="comment"> *</span>
<a name="l00576"></a>00576 <span class="comment"> * \endcode</span>
<a name="l00577"></a>00577 <span class="comment"> */</span>
<a name="l00578"></a>00578 <span class="keyword">template</span> <<span class="keyword">typename</span> Distance, <span class="keyword">class </span>DatasetAdaptor,<span class="keywordtype">int</span> DIM = -1>
<a name="l00579"></a>00579 <span class="keyword">class </span>KDTreeSingleIndexAdaptor
<a name="l00580"></a>00580 {
<a name="l00581"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">00581</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> Distance<a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">::ElementType</a> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a>;
<a name="l00582"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">00582</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> Distance::ResultType <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">DistanceType</a>;
<a name="l00583"></a>00583 <span class="comment"></span>
<a name="l00584"></a>00584 <span class="comment"> /**</span>
<a name="l00585"></a>00585 <span class="comment"> * Array of indices to vectors in the dataset.</span>
<a name="l00586"></a>00586 <span class="comment"> */</span>
<a name="l00587"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ade22cc465a0105733f5d5a2805e7735c">00587</a> std::vector<int> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ade22cc465a0105733f5d5a2805e7735c" title="Array of indices to vectors in the dataset.">vind</a>;
<a name="l00588"></a>00588
<a name="l00589"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a4b925cfecaefd01e828f8f7ef30501d5">00589</a> <span class="keywordtype">int</span> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a4b925cfecaefd01e828f8f7ef30501d5">leaf_max_size_</a>;
<a name="l00590"></a>00590
<a name="l00591"></a>00591 <span class="comment"></span>
<a name="l00592"></a>00592 <span class="comment"> /**</span>
<a name="l00593"></a>00593 <span class="comment"> * The dataset used by this index</span>
<a name="l00594"></a>00594 <span class="comment"> */</span>
<a name="l00595"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ab75797e3d3ce9b230b302c280f89474c">00595</a> <span class="keyword">const</span> DatasetAdaptor &<a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ab75797e3d3ce9b230b302c280f89474c" title="The dataset used by this index.">dataset</a>; <span class="comment">//!< The source of our data</span>
<a name="l00596"></a>00596 <span class="comment"></span>
<a name="l00597"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a7419d9e0afc13cf75433f37087026d46">00597</a> <span class="keyword">const</span> <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_params.html" title="Parameters.">KDTreeSingleIndexAdaptorParams</a> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a7419d9e0afc13cf75433f37087026d46">index_params</a>;
<a name="l00598"></a>00598
<a name="l00599"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6694660fb4fcf93ef2351e2c31b35473">00599</a> <span class="keywordtype">int</span> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6694660fb4fcf93ef2351e2c31b35473">size_</a>;
<a name="l00600"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ac0c5e3331356e68a7b658ccd950af75b">00600</a> <span class="keywordtype">int</span> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ac0c5e3331356e68a7b658ccd950af75b">dim</a>;
<a name="l00601"></a>00601
<a name="l00602"></a>00602
<a name="l00603"></a>00603 <span class="comment">/*--------------------- Internal Data Structures --------------------------*/</span>
<a name="l00604"></a>00604 <span class="keyword">struct </span><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html">Node</a>
<a name="l00605"></a>00605 {
<a name="l00606"></a>00606 <span class="keyword">union </span>{
<a name="l00607"></a>00607 <span class="keyword">struct</span>
<a name="l00608"></a>00608 {<span class="comment"></span>
<a name="l00609"></a>00609 <span class="comment"> /**</span>
<a name="l00610"></a>00610 <span class="comment"> * Indices of points in leaf node</span>
<a name="l00611"></a>00611 <span class="comment"> */</span>
<a name="l00612"></a><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a96e5e8b3c072c8f6db6abad1778fa3fa">00612</a> <span class="keywordtype">int</span> left, <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a96e5e8b3c072c8f6db6abad1778fa3fa">right</a>;
<a name="l00613"></a>00613 } lr;
<a name="l00614"></a>00614 <span class="keyword">struct</span>
<a name="l00615"></a>00615 {<span class="comment"></span>
<a name="l00616"></a>00616 <span class="comment"> /**</span>
<a name="l00617"></a>00617 <span class="comment"> * Dimension used for subdivision.</span>
<a name="l00618"></a>00618 <span class="comment"> */</span>
<a name="l00619"></a><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a46a5acacde9acc88b4cd9baf5c9bd47b">00619</a> <span class="keywordtype">int</span> <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a46a5acacde9acc88b4cd9baf5c9bd47b" title="Dimension used for subdivision.">divfeat</a>;<span class="comment"></span>
<a name="l00620"></a>00620 <span class="comment"> /**</span>
<a name="l00621"></a>00621 <span class="comment"> * The values used for subdivision.</span>
<a name="l00622"></a>00622 <span class="comment"> */</span>
<a name="l00623"></a><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a3c1a04f4a4d962052b086de7d99f3999">00623</a> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">DistanceType</a> <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a3c1a04f4a4d962052b086de7d99f3999" title="The values used for subdivision.">divlow</a>, divhigh;
<a name="l00624"></a>00624 } sub;
<a name="l00625"></a>00625 };<span class="comment"></span>
<a name="l00626"></a>00626 <span class="comment"> /**</span>
<a name="l00627"></a>00627 <span class="comment"> * The child nodes.</span>
<a name="l00628"></a>00628 <span class="comment"> */</span>
<a name="l00629"></a><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#acc45092cb923a11d9317590be29b5dc4">00629</a> <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html">Node</a>* child1, * <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#acc45092cb923a11d9317590be29b5dc4">child2</a>;
<a name="l00630"></a>00630 };
<a name="l00631"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a3bf8e168a72b079f50d104b2e526e3bc">00631</a> <span class="keyword">typedef</span> <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html">Node</a>* <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a3bf8e168a72b079f50d104b2e526e3bc">NodePtr</a>;
<a name="l00632"></a>00632
<a name="l00633"></a>00633
<a name="l00634"></a>00634 <span class="keyword">struct </span><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_interval.html">Interval</a>
<a name="l00635"></a>00635 {
<a name="l00636"></a><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_interval.html#a36aadfccaca2891340c1fdcec305e702">00636</a> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a> <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_interval.html#a36aadfccaca2891340c1fdcec305e702">low</a>, high;
<a name="l00637"></a>00637 };
<a name="l00638"></a>00638
<a name="l00639"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a69a9111665626fbebca0231426eb76cf">00639</a> <span class="keyword">typedef</span> std::vector<Interval> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a69a9111665626fbebca0231426eb76cf">BoundingBox</a>;
<a name="l00640"></a>00640
<a name="l00641"></a>00641 <span class="comment"></span>
<a name="l00642"></a>00642 <span class="comment"> /** This record represents a branch point when finding neighbors in</span>
<a name="l00643"></a>00643 <span class="comment"> the tree. It contains a record of the minimum distance to the query</span>
<a name="l00644"></a>00644 <span class="comment"> point, as well as the node at which the search resumes.</span>
<a name="l00645"></a>00645 <span class="comment"> */</span>
<a name="l00646"></a>00646 <span class="keyword">template</span> <<span class="keyword">typename</span> T, <span class="keyword">typename</span> DistanceType>
<a name="l00647"></a>00647 <span class="keyword">struct </span><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_branch_struct.html" title="This record represents a branch point when finding neighbors in the tree.">BranchStruct</a>
<a name="l00648"></a>00648 {
<a name="l00649"></a><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_branch_struct.html#a31b99a9238363f0291df43ff6fa8f6d7">00649</a> T <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_branch_struct.html#a31b99a9238363f0291df43ff6fa8f6d7">node</a>; <span class="comment">/* Tree node at which search resumes */</span>
<a name="l00650"></a><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_branch_struct.html#a49725938b52e7d18edd46965e98be165">00650</a> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">DistanceType</a> <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_branch_struct.html#a49725938b52e7d18edd46965e98be165">mindist</a>; <span class="comment">/* Minimum distance to query for all nodes below. */</span>
<a name="l00651"></a>00651
<a name="l00652"></a><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_branch_struct.html#a47f9ec7779e7c33067fc4b3a4a46885c">00652</a> <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_branch_struct.html#a47f9ec7779e7c33067fc4b3a4a46885c">BranchStruct</a>() {}
<a name="l00653"></a><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_branch_struct.html#ab06fa55cd16afa9c5c2ff294ff02a8af">00653</a> <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_branch_struct.html#ab06fa55cd16afa9c5c2ff294ff02a8af">BranchStruct</a>(<span class="keyword">const</span> T& aNode, <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">DistanceType</a> dist) : node(aNode), mindist(dist) {}
<a name="l00654"></a>00654
<a name="l00655"></a><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_branch_struct.html#ab961468135dd5d2f9e6cbbb264351153">00655</a> <span class="keywordtype">bool</span> operator<(const BranchStruct<T, DistanceType>& rhs) <span class="keyword">const</span>
<a name="l00656"></a>00656 {
<a name="l00657"></a>00657 <span class="keywordflow">return</span> mindist<rhs.mindist;
<a name="l00658"></a>00658 }
<a name="l00659"></a>00659 };
<a name="l00660"></a>00660 <span class="comment"></span>
<a name="l00661"></a>00661 <span class="comment"> /**</span>
<a name="l00662"></a>00662 <span class="comment"> * Array of k-d trees used to find neighbours.</span>
<a name="l00663"></a>00663 <span class="comment"> */</span>
<a name="l00664"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a70dc661a5321eeee84615e61dee72d38">00664</a> <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html">NodePtr</a> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a70dc661a5321eeee84615e61dee72d38" title="Array of k-d trees used to find neighbours.">root_node</a>;
<a name="l00665"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a44cfc5a539d278b67ec7aae434c428a5">00665</a> <span class="keyword">typedef</span> <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_branch_struct.html" title="This record represents a branch point when finding neighbors in the tree.">BranchStruct<NodePtr, DistanceType></a> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a44cfc5a539d278b67ec7aae434c428a5">BranchSt</a>;
<a name="l00666"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#aa5fa781fca2d8b0e3704f0782333c566">00666</a> <span class="keyword">typedef</span> <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_branch_struct.html" title="This record represents a branch point when finding neighbors in the tree.">BranchSt</a>* <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#aa5fa781fca2d8b0e3704f0782333c566">Branch</a>;
<a name="l00667"></a>00667
<a name="l00668"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a137f3db080f1f4b891049b46ac6eac15">00668</a> <a class="code" href="classstd_1_1vector.html">BoundingBox</a> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a137f3db080f1f4b891049b46ac6eac15">root_bbox</a>;
<a name="l00669"></a>00669 <span class="comment"></span>
<a name="l00670"></a>00670 <span class="comment"> /**</span>
<a name="l00671"></a>00671 <span class="comment"> * Pooled memory allocator.</span>
<a name="l00672"></a>00672 <span class="comment"> *</span>
<a name="l00673"></a>00673 <span class="comment"> * Using a pooled memory allocator is more efficient</span>
<a name="l00674"></a>00674 <span class="comment"> * than allocating memory directly when there is a large</span>
<a name="l00675"></a>00675 <span class="comment"> * number small of memory allocations.</span>
<a name="l00676"></a>00676 <span class="comment"> */</span>
<a name="l00677"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a65dd6389fd3369f779ab913b0321042a">00677</a> <a class="code" href="classnanoflann_1_1_pooled_allocator.html">PooledAllocator</a> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a65dd6389fd3369f779ab913b0321042a" title="Pooled memory allocator.">pool</a>;
<a name="l00678"></a>00678
<a name="l00679"></a>00679 <span class="keyword">public</span>:
<a name="l00680"></a>00680
<a name="l00681"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#aa2eec2ed9ff1fac56fcc90f4a7a27ff7">00681</a> Distance <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#aa2eec2ed9ff1fac56fcc90f4a7a27ff7">distance</a>;
<a name="l00682"></a>00682 <span class="comment"></span>
<a name="l00683"></a>00683 <span class="comment"> /**</span>
<a name="l00684"></a>00684 <span class="comment"> * KDTree constructor</span>
<a name="l00685"></a>00685 <span class="comment"> *</span>
<a name="l00686"></a>00686 <span class="comment"> * Params:</span>
<a name="l00687"></a>00687 <span class="comment"> * inputData = dataset with the input features</span>
<a name="l00688"></a>00688 <span class="comment"> * params = parameters passed to the kdtree algorithm</span>
<a name="l00689"></a>00689 <span class="comment"> */</span>
<a name="l00690"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a4848332eaa0f21e6cdfeb419effea381">00690</a> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html" title="kd-tree index">KDTreeSingleIndexAdaptor</a>(<span class="keyword">const</span> <span class="keywordtype">int</span> dimensionality, <span class="keyword">const</span> DatasetAdaptor& inputData, <span class="keyword">const</span> <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_params.html" title="Parameters.">KDTreeSingleIndexAdaptorParams</a>& params = <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_params.html" title="Parameters.">KDTreeSingleIndexAdaptorParams</a>() ) :
<a name="l00691"></a>00691 dataset(inputData), index_params(params), <a class="code" href="group__geometry__grp.html#ga8c0a76e906f12560cfa49fcd269c8398" title="Gets the distance between two points in a 2D space.">distance</a>(inputData)
<a name="l00692"></a>00692 {
<a name="l00693"></a>00693 size_ = <span class="keyword">static_cast<</span><span class="keywordtype">int</span><span class="keyword">></span>(dataset.kdtree_get_point_count());
<a name="l00694"></a>00694 dim = dimensionality;
<a name="l00695"></a>00695 <span class="keywordflow">if</span> (DIM>0) dim=DIM;
<a name="l00696"></a>00696 <span class="keywordflow">else</span> {
<a name="l00697"></a>00697 <span class="keywordflow">if</span> (params.dim>0) dim = params.dim;
<a name="l00698"></a>00698 }
<a name="l00699"></a>00699 leaf_max_size_ = params.leaf_max_size;
<a name="l00700"></a>00700
<a name="l00701"></a>00701 <span class="comment">// Create a permutable array of indices to the input vectors.</span>
<a name="l00702"></a>00702 vind.resize(size_);
<a name="l00703"></a>00703 <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = 0; i < size_; i++) {
<a name="l00704"></a>00704 vind[i] = i;
<a name="l00705"></a>00705 }
<a name="l00706"></a>00706 }
<a name="l00707"></a>00707 <span class="comment"></span>
<a name="l00708"></a>00708 <span class="comment"> /**</span>
<a name="l00709"></a>00709 <span class="comment"> * Standard destructor</span>
<a name="l00710"></a>00710 <span class="comment"> */</span>
<a name="l00711"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a006f508a2709ad21db133f53b568c95c">00711</a> ~<a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html" title="kd-tree index">KDTreeSingleIndexAdaptor</a>()
<a name="l00712"></a>00712 {
<a name="l00713"></a>00713 }
<a name="l00714"></a>00714 <span class="comment"></span>
<a name="l00715"></a>00715 <span class="comment"> /**</span>
<a name="l00716"></a>00716 <span class="comment"> * Builds the index</span>
<a name="l00717"></a>00717 <span class="comment"> */</span>
<a name="l00718"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#aca790689af0e1cacb97c1702bca7e801">00718</a> <span class="keywordtype">void</span> buildIndex()
<a name="l00719"></a>00719 {
<a name="l00720"></a>00720 computeBoundingBox(root_bbox);
<a name="l00721"></a>00721 root_node = divideTree(0, size_, root_bbox ); <span class="comment">// construct the tree</span>
<a name="l00722"></a>00722 }
<a name="l00723"></a>00723 <span class="comment"></span>
<a name="l00724"></a>00724 <span class="comment"> /**</span>
<a name="l00725"></a>00725 <span class="comment"> * Returns size of index.</span>
<a name="l00726"></a>00726 <span class="comment"> */</span>
<a name="l00727"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a69ade412e55d0e64b20e017809ca87ee">00727</a> <span class="keywordtype">size_t</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a1ccd37d4307264f3c70abb55dc5d57e1">size</a>()<span class="keyword"> const</span>
<a name="l00728"></a>00728 <span class="keyword"> </span>{
<a name="l00729"></a>00729 <span class="keywordflow">return</span> size_;
<a name="l00730"></a>00730 }
<a name="l00731"></a>00731 <span class="comment"></span>
<a name="l00732"></a>00732 <span class="comment"> /**</span>
<a name="l00733"></a>00733 <span class="comment"> * Returns the length of an index feature.</span>
<a name="l00734"></a>00734 <span class="comment"> */</span>
<a name="l00735"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a226820ee2ad26a5ca3d559a3ac84a88b">00735</a> <span class="keywordtype">size_t</span> veclen()<span class="keyword"> const</span>
<a name="l00736"></a>00736 <span class="keyword"> </span>{
<a name="l00737"></a>00737 <span class="keywordflow">return</span> (DIM>0 ? DIM : dim);
<a name="l00738"></a>00738 }
<a name="l00739"></a>00739 <span class="comment"></span>
<a name="l00740"></a>00740 <span class="comment"> /**</span>
<a name="l00741"></a>00741 <span class="comment"> * Computes the inde memory usage</span>
<a name="l00742"></a>00742 <span class="comment"> * Returns: memory used by the index</span>
<a name="l00743"></a>00743 <span class="comment"> */</span>
<a name="l00744"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ac5c1431f7adbabe16ef58d67ff2a369c">00744</a> <span class="keywordtype">int</span> usedMemory()<span class="keyword"> const</span>
<a name="l00745"></a>00745 <span class="keyword"> </span>{
<a name="l00746"></a>00746 <span class="keywordflow">return</span> pool.usedMemory+pool.wastedMemory+dataset.kdtree_get_point_count()*<span class="keyword">sizeof</span>(int); <span class="comment">// pool memory and vind array memory</span>
<a name="l00747"></a>00747 }
<a name="l00748"></a>00748 <span class="comment"></span>
<a name="l00749"></a>00749 <span class="comment"> /** \name Query methods</span>
<a name="l00750"></a>00750 <span class="comment"> * @{ */</span>
<a name="l00751"></a>00751 <span class="comment"></span>
<a name="l00752"></a>00752 <span class="comment"> /**</span>
<a name="l00753"></a>00753 <span class="comment"> * Find set of nearest neighbors to vec[0:dim-1]. Their indices are stored inside</span>
<a name="l00754"></a>00754 <span class="comment"> * the result object.</span>
<a name="l00755"></a>00755 <span class="comment"> *</span>
<a name="l00756"></a>00756 <span class="comment"> * Params:</span>
<a name="l00757"></a>00757 <span class="comment"> * result = the result object in which the indices of the nearest-neighbors are stored</span>
<a name="l00758"></a>00758 <span class="comment"> * vec = the vector for which to search the nearest neighbors</span>
<a name="l00759"></a>00759 <span class="comment"> * maxCheck = the maximum number of restarts (in a best-bin-first manner)</span>
<a name="l00760"></a>00760 <span class="comment"> *</span>
<a name="l00761"></a>00761 <span class="comment"> * \tparam RESULTSET Should be any ResultSet<DistanceType></span>
<a name="l00762"></a>00762 <span class="comment"> * \sa knnSearch, radiusSearch</span>
<a name="l00763"></a>00763 <span class="comment"> */</span>
<a name="l00764"></a>00764 <span class="keyword">template</span> <<span class="keyword">typename</span> RESULTSET>
<a name="l00765"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a993c2f92163508dee0b2ea7240758788">00765</a> <span class="keywordtype">void</span> findNeighbors(RESULTSET& result, <span class="keyword">const</span> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a>* vec, <span class="keyword">const</span> <a class="code" href="structnanoflann_1_1_search_params.html" title="Search options for KDTreeSingleIndexAdaptor::findNeighbors()">SearchParams</a>& searchParams)<span class="keyword"> const</span>
<a name="l00766"></a>00766 <span class="keyword"> </span>{
<a name="l00767"></a>00767 <span class="keywordtype">float</span> epsError = 1+searchParams.<a class="code" href="structnanoflann_1_1_search_params.html#a64b9e7c56bbb743694f6188f616a94cc" title="search for eps-approximate neighbours (default: 0)">eps</a>;
<a name="l00768"></a>00768
<a name="l00769"></a>00769 std::vector<DistanceType> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a9e5955301b936a6ba02bf179201a0793">dists</a>( (DIM>0 ? DIM : dim) ,0);
<a name="l00770"></a>00770 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">DistanceType</a> distsq = computeInitialDistances(vec, dists);
<a name="l00771"></a>00771 <span class="keywordtype">int</span> count_leaf = 0;
<a name="l00772"></a>00772 searchLevel(result, vec, root_node, distsq, dists, epsError,count_leaf);
<a name="l00773"></a>00773 }
<a name="l00774"></a>00774 <span class="comment"></span>
<a name="l00775"></a>00775 <span class="comment"> /**</span>
<a name="l00776"></a>00776 <span class="comment"> * Find the "num_closest" nearest neighbors to the \a query_point[0:dim-1]. Their indices are stored inside</span>
<a name="l00777"></a>00777 <span class="comment"> * the result object.</span>
<a name="l00778"></a>00778 <span class="comment"> * \sa radiusSearch, findNeighbors</span>
<a name="l00779"></a>00779 <span class="comment"> */</span>
<a name="l00780"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a1d10f4eee8eb2d8fd1cbdd8f680a0e60">00780</a> <span class="keyword">inline</span> <span class="keywordtype">void</span> knnSearch(<span class="keyword">const</span> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a> *query_point, <span class="keywordtype">int</span> num_closest, <span class="keywordtype">int</span> *out_indices, <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a> *out_distances_sq, <span class="keyword">const</span> <span class="keywordtype">int</span> nChecks = 10)<span class="keyword"> const</span>
<a name="l00781"></a>00781 <span class="keyword"> </span>{
<a name="l00782"></a>00782 nanoflann<a class="code" href="classnanoflann_1_1_k_n_n_result_set.html">::KNNResultSet<ElementType></a> resultSet(num_closest);
<a name="l00783"></a>00783 resultSet.<a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a4fefecb0ff9480ceeb1212afa67f9966">init</a>(out_indices, out_distances_sq);
<a name="l00784"></a>00784 this->findNeighbors(resultSet, query_point, <a class="code" href="structnanoflann_1_1_search_params.html" title="Search options for KDTreeSingleIndexAdaptor::findNeighbors()">nanoflann::SearchParams</a>(nChecks));
<a name="l00785"></a>00785 }
<a name="l00786"></a>00786 <span class="comment"></span>
<a name="l00787"></a>00787 <span class="comment"> /**</span>
<a name="l00788"></a>00788 <span class="comment"> * Find all the neighbors to \a query_point[0:dim-1] within a maximum radius.</span>
<a name="l00789"></a>00789 <span class="comment"> * The output is given as a vector of pairs, of which the first element is a point index and the second the corresponding distance.</span>
<a name="l00790"></a>00790 <span class="comment"> * Previous contents of \a IndicesDists are cleared.</span>
<a name="l00791"></a>00791 <span class="comment"> *</span>
<a name="l00792"></a>00792 <span class="comment"> * If searchParams.sorted==true, the output list is sorted by ascending distances.</span>
<a name="l00793"></a>00793 <span class="comment"> *</span>
<a name="l00794"></a>00794 <span class="comment"> * For a better performance, it is advisable to do a .reserve() on the vector if you have any wild guess about the number of expected matches.</span>
<a name="l00795"></a>00795 <span class="comment"> *</span>
<a name="l00796"></a>00796 <span class="comment"> * \sa knnSearch, findNeighbors</span>
<a name="l00797"></a>00797 <span class="comment"> * \return The number of points within the given radius (i.e. indices.size() or dists.size() )</span>
<a name="l00798"></a>00798 <span class="comment"> */</span>
<a name="l00799"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#af38434c674cac047f8d2f297ce1f5178">00799</a> <span class="keywordtype">size_t</span> radiusSearch(<span class="keyword">const</span> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a> *query_point,<span class="keyword">const</span> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">DistanceType</a> radius, <a class="code" href="classstd_1_1vector.html" title="STL class.">std::vector</a><std::pair<int,DistanceType> >& IndicesDists, <span class="keyword">const</span> <a class="code" href="structnanoflann_1_1_search_params.html" title="Search options for KDTreeSingleIndexAdaptor::findNeighbors()">SearchParams</a>& searchParams)<span class="keyword"> const</span>
<a name="l00800"></a>00800 <span class="keyword"> </span>{
<a name="l00801"></a>00801 <a class="code" href="classnanoflann_1_1_radius_result_set.html" title="A result-set class used when performing a radius based search.">RadiusResultSet<DistanceType></a> resultSet(radius,IndicesDists);
<a name="l00802"></a>00802 this->findNeighbors(resultSet, query_point, searchParams);
<a name="l00803"></a>00803
<a name="l00804"></a>00804 <span class="keywordflow">if</span> (searchParams.<a class="code" href="structnanoflann_1_1_search_params.html#a5126d5f71f1c9163c6a581776a0e9466" title="only for radius search, require neighbours sorted by distance (default: true)">sorted</a>)
<a name="l00805"></a>00805 std::sort(IndicesDists.begin(),IndicesDists.end(), <a class="code" href="structnanoflann_1_1_index_dist___sorter.html" title="operator "<" for std::sort()">IndexDist_Sorter<DistanceType></a>() );
<a name="l00806"></a>00806
<a name="l00807"></a>00807 <span class="keywordflow">return</span> resultSet.size();
<a name="l00808"></a>00808 }
<a name="l00809"></a>00809 <span class="comment"></span>
<a name="l00810"></a>00810 <span class="comment"> /** @} */</span>
<a name="l00811"></a>00811
<a name="l00812"></a>00812 <span class="keyword">private</span>:
<a name="l00813"></a>00813 <span class="comment"></span>
<a name="l00814"></a>00814 <span class="comment"> /// Helper accessor to the dataset points:</span>
<a name="l00815"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a851e4a0c4d7aa40f08a57ee42cc869cf">00815</a> <span class="comment"></span> <span class="keyword">inline</span> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a851e4a0c4d7aa40f08a57ee42cc869cf" title="Helper accessor to the dataset points:">dataset_get</a>(<span class="keywordtype">size_t</span> idx, <span class="keywordtype">int</span> component)<span class="keyword"> const </span>{
<a name="l00816"></a>00816 <span class="keywordflow">return</span> dataset.kdtree_get_pt(idx,component);
<a name="l00817"></a>00817 }
<a name="l00818"></a>00818
<a name="l00819"></a>00819
<a name="l00820"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a2ad8974bea65453783163ff3150a7a38">00820</a> <span class="keywordtype">void</span> save_tree(FILE* stream, <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html">NodePtr</a> tree)
<a name="l00821"></a>00821 {
<a name="l00822"></a>00822 <a class="code" href="group__loadsave__grp.html#ga4eb2ec6a057da0c432ddc374800fc6ec">save_value</a>(stream, *tree);
<a name="l00823"></a>00823 <span class="keywordflow">if</span> (tree-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a9f89ac3385c57d8a735a4d9004bf5d6b" title="The child nodes.">child1</a>!=NULL) {
<a name="l00824"></a>00824 save_tree(stream, tree-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a9f89ac3385c57d8a735a4d9004bf5d6b" title="The child nodes.">child1</a>);
<a name="l00825"></a>00825 }
<a name="l00826"></a>00826 <span class="keywordflow">if</span> (tree-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#acc45092cb923a11d9317590be29b5dc4">child2</a>!=NULL) {
<a name="l00827"></a>00827 save_tree(stream, tree-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#acc45092cb923a11d9317590be29b5dc4">child2</a>);
<a name="l00828"></a>00828 }
<a name="l00829"></a>00829 }
<a name="l00830"></a>00830
<a name="l00831"></a>00831
<a name="l00832"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a721d1e86474196928d6f7c95d2b13168">00832</a> <span class="keywordtype">void</span> load_tree(FILE* stream, <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html">NodePtr</a>& tree)
<a name="l00833"></a>00833 {
<a name="l00834"></a>00834 tree = pool.allocate<<a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html">Node</a>>();
<a name="l00835"></a>00835 <a class="code" href="group__loadsave__grp.html#ga8c271fd91a22446d477ef32aac2dce98">load_value</a>(stream, *tree);
<a name="l00836"></a>00836 <span class="keywordflow">if</span> (tree-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a9f89ac3385c57d8a735a4d9004bf5d6b" title="The child nodes.">child1</a>!=NULL) {
<a name="l00837"></a>00837 load_tree(stream, tree-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a9f89ac3385c57d8a735a4d9004bf5d6b" title="The child nodes.">child1</a>);
<a name="l00838"></a>00838 }
<a name="l00839"></a>00839 <span class="keywordflow">if</span> (tree-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#acc45092cb923a11d9317590be29b5dc4">child2</a>!=NULL) {
<a name="l00840"></a>00840 load_tree(stream, tree-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#acc45092cb923a11d9317590be29b5dc4">child2</a>);
<a name="l00841"></a>00841 }
<a name="l00842"></a>00842 }
<a name="l00843"></a>00843
<a name="l00844"></a>00844
<a name="l00845"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a2ba88e4d33cdd00c13663bffd2bd301a">00845</a> <span class="keywordtype">void</span> computeBoundingBox(<a class="code" href="classstd_1_1vector.html">BoundingBox</a>& bbox)
<a name="l00846"></a>00846 {
<a name="l00847"></a>00847 bbox.resize((DIM>0 ? DIM : dim));
<a name="l00848"></a>00848 <span class="keywordflow">if</span> (dataset.kdtree_get_bbox(bbox))
<a name="l00849"></a>00849 {
<a name="l00850"></a>00850 <span class="comment">// Done! It was implemented in derived class</span>
<a name="l00851"></a>00851 }
<a name="l00852"></a>00852 <span class="keywordflow">else</span>
<a name="l00853"></a>00853 {
<a name="l00854"></a>00854 <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i=0; i<(DIM>0 ? DIM : dim); ++i) {
<a name="l00855"></a>00855 bbox[i].low =
<a name="l00856"></a>00856 bbox[i].high = dataset_get(0,i);
<a name="l00857"></a>00857 }
<a name="l00858"></a>00858 <span class="keyword">const</span> <span class="keywordtype">size_t</span> N = dataset.kdtree_get_point_count();
<a name="l00859"></a>00859 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> k=1; k<N; ++k) {
<a name="l00860"></a>00860 <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i=0; i<(DIM>0 ? DIM : dim); ++i) {
<a name="l00861"></a>00861 <span class="keywordflow">if</span> (dataset_get(k,i)<bbox[i].low) bbox[i].low = dataset_get(k,i);
<a name="l00862"></a>00862 <span class="keywordflow">if</span> (dataset_get(k,i)>bbox[i].high) bbox[i].high = dataset_get(k,i);
<a name="l00863"></a>00863 }
<a name="l00864"></a>00864 }
<a name="l00865"></a>00865 }
<a name="l00866"></a>00866 }
<a name="l00867"></a>00867
<a name="l00868"></a>00868 <span class="comment"></span>
<a name="l00869"></a>00869 <span class="comment"> /**</span>
<a name="l00870"></a>00870 <span class="comment"> * Create a tree node that subdivides the list of vecs from vind[first]</span>
<a name="l00871"></a>00871 <span class="comment"> * to vind[last]. The routine is called recursively on each sublist.</span>
<a name="l00872"></a>00872 <span class="comment"> * Place a pointer to this new tree node in the location pTree.</span>
<a name="l00873"></a>00873 <span class="comment"> *</span>
<a name="l00874"></a>00874 <span class="comment"> * Params: pTree = the new node to create</span>
<a name="l00875"></a>00875 <span class="comment"> * first = index of the first vector</span>
<a name="l00876"></a>00876 <span class="comment"> * last = index of the last vector</span>
<a name="l00877"></a>00877 <span class="comment"> */</span>
<a name="l00878"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a2a30a300ecc5e9fd837688dd8c4b807c">00878</a> <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html">NodePtr</a> divideTree(<span class="keywordtype">int</span> left, <span class="keywordtype">int</span> right, <a class="code" href="classstd_1_1vector.html">BoundingBox</a>& bbox)
<a name="l00879"></a>00879 {
<a name="l00880"></a>00880 <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html">NodePtr</a> node = pool.allocate<<a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html">Node</a>>(); <span class="comment">// allocate memory</span>
<a name="l00881"></a>00881
<a name="l00882"></a>00882 <span class="comment">/* If too few exemplars remain, then make this a leaf node. */</span>
<a name="l00883"></a>00883 <span class="keywordflow">if</span> ( (right-left) <= leaf_max_size_) {
<a name="l00884"></a>00884 node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a9f89ac3385c57d8a735a4d9004bf5d6b" title="The child nodes.">child1</a> = node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#acc45092cb923a11d9317590be29b5dc4">child2</a> = NULL; <span class="comment">/* Mark as leaf node. */</span>
<a name="l00885"></a>00885 node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a4af2b70f9aa82818ea759b65e791f8b3">lr</a>.left = left;
<a name="l00886"></a>00886 node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a4af2b70f9aa82818ea759b65e791f8b3">lr</a>.right = right;
<a name="l00887"></a>00887
<a name="l00888"></a>00888 <span class="comment">// compute bounding-box of leaf points</span>
<a name="l00889"></a>00889 <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i=0; i<(DIM>0 ? DIM : dim); ++i) {
<a name="l00890"></a>00890 bbox[i].low = dataset_get(vind[left],i);
<a name="l00891"></a>00891 bbox[i].high = dataset_get(vind[left],i);
<a name="l00892"></a>00892 }
<a name="l00893"></a>00893 <span class="keywordflow">for</span> (<span class="keywordtype">int</span> k=left+1; k<right; ++k) {
<a name="l00894"></a>00894 <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i=0; i<(DIM>0 ? DIM : dim); ++i) {
<a name="l00895"></a>00895 <span class="keywordflow">if</span> (bbox[i].low>dataset_get(vind[k],i)) bbox[i].low=dataset_get(vind[k],i);
<a name="l00896"></a>00896 <span class="keywordflow">if</span> (bbox[i].high<dataset_get(vind[k],i)) bbox[i].high=dataset_get(vind[k],i);
<a name="l00897"></a>00897 }
<a name="l00898"></a>00898 }
<a name="l00899"></a>00899 }
<a name="l00900"></a>00900 <span class="keywordflow">else</span> {
<a name="l00901"></a>00901 <span class="keywordtype">int</span> idx;
<a name="l00902"></a>00902 <span class="keywordtype">int</span> cutfeat;
<a name="l00903"></a>00903 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">DistanceType</a> cutval;
<a name="l00904"></a>00904 middleSplit_(&vind[0]+left, right-left, idx, cutfeat, cutval, bbox);
<a name="l00905"></a>00905
<a name="l00906"></a>00906 node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a47fda7bcb8c3237bc347aeac21ad2817">sub</a>.divfeat = cutfeat;
<a name="l00907"></a>00907
<a name="l00908"></a>00908 <a class="code" href="classstd_1_1vector.html">BoundingBox</a> left_bbox(bbox);
<a name="l00909"></a>00909 left_bbox[cutfeat].high = cutval;
<a name="l00910"></a>00910 node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a9f89ac3385c57d8a735a4d9004bf5d6b" title="The child nodes.">child1</a> = divideTree(left, left+idx, left_bbox);
<a name="l00911"></a>00911
<a name="l00912"></a>00912 <a class="code" href="classstd_1_1vector.html">BoundingBox</a> right_bbox(bbox);
<a name="l00913"></a>00913 right_bbox[cutfeat].low = cutval;
<a name="l00914"></a>00914 node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#acc45092cb923a11d9317590be29b5dc4">child2</a> = divideTree(left+idx, right, right_bbox);
<a name="l00915"></a>00915
<a name="l00916"></a>00916 node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a47fda7bcb8c3237bc347aeac21ad2817">sub</a>.divlow = left_bbox[cutfeat].high;
<a name="l00917"></a>00917 node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a47fda7bcb8c3237bc347aeac21ad2817">sub</a>.divhigh = right_bbox[cutfeat].low;
<a name="l00918"></a>00918
<a name="l00919"></a>00919 <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i=0; i<(DIM>0 ? DIM : dim); ++i) {
<a name="l00920"></a>00920 bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
<a name="l00921"></a>00921 bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
<a name="l00922"></a>00922 }
<a name="l00923"></a>00923 }
<a name="l00924"></a>00924
<a name="l00925"></a>00925 <span class="keywordflow">return</span> node;
<a name="l00926"></a>00926 }
<a name="l00927"></a>00927
<a name="l00928"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a7f7121b101dfe0651b80653bcc58bd1a">00928</a> <span class="keywordtype">void</span> computeMinMax(<span class="keywordtype">int</span>* ind, <span class="keywordtype">int</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">count</a>, <span class="keywordtype">int</span> element, <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a>& min_elem, <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a>& max_elem)
<a name="l00929"></a>00929 {
<a name="l00930"></a>00930 min_elem = dataset_get(ind[0],element);
<a name="l00931"></a>00931 max_elem = dataset_get(ind[0],element);
<a name="l00932"></a>00932 <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i=1; i<<a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">count</a>; ++i) {
<a name="l00933"></a>00933 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a> val = dataset_get(ind[i],element);
<a name="l00934"></a>00934 <span class="keywordflow">if</span> (val<min_elem) min_elem = val;
<a name="l00935"></a>00935 <span class="keywordflow">if</span> (val>max_elem) max_elem = val;
<a name="l00936"></a>00936 }
<a name="l00937"></a>00937 }
<a name="l00938"></a>00938
<a name="l00939"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a7df2741d46afbfe9739eee0015c12fbd">00939</a> <span class="keywordtype">void</span> middleSplit(<span class="keywordtype">int</span>* ind, <span class="keywordtype">int</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">count</a>, <span class="keywordtype">int</span>& index, <span class="keywordtype">int</span>& cutfeat, <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">DistanceType</a>& cutval, <span class="keyword">const</span> <a class="code" href="classstd_1_1vector.html">BoundingBox</a>& bbox)
<a name="l00940"></a>00940 {
<a name="l00941"></a>00941 <span class="comment">// find the largest span from the approximate bounding box</span>
<a name="l00942"></a>00942 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a> max_span = bbox[0].high-bbox[0].low;
<a name="l00943"></a>00943 cutfeat = 0;
<a name="l00944"></a>00944 cutval = (bbox[0].high+bbox[0].low)/2;
<a name="l00945"></a>00945 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> i=1; i<(DIM>0 ? DIM : dim); ++i) {
<a name="l00946"></a>00946 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a> span = bbox[i].low-bbox[i].low;
<a name="l00947"></a>00947 <span class="keywordflow">if</span> (span>max_span) {
<a name="l00948"></a>00948 max_span = span;
<a name="l00949"></a>00949 cutfeat = i;
<a name="l00950"></a>00950 cutval = (bbox[i].high+bbox[i].low)/2;
<a name="l00951"></a>00951 }
<a name="l00952"></a>00952 }
<a name="l00953"></a>00953
<a name="l00954"></a>00954 <span class="comment">// compute exact span on the found dimension</span>
<a name="l00955"></a>00955 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a> min_elem, max_elem;
<a name="l00956"></a>00956 computeMinMax(ind, count, cutfeat, min_elem, max_elem);
<a name="l00957"></a>00957 cutval = (min_elem+max_elem)/2;
<a name="l00958"></a>00958 max_span = max_elem - min_elem;
<a name="l00959"></a>00959
<a name="l00960"></a>00960 <span class="comment">// check if a dimension of a largest span exists</span>
<a name="l00961"></a>00961 <span class="keywordtype">size_t</span> k = cutfeat;
<a name="l00962"></a>00962 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> i=0; i<(DIM>0 ? DIM : dim); ++i) {
<a name="l00963"></a>00963 <span class="keywordflow">if</span> (i==k) <span class="keywordflow">continue</span>;
<a name="l00964"></a>00964 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a> span = bbox[i].high-bbox[i].low;
<a name="l00965"></a>00965 <span class="keywordflow">if</span> (span>max_span) {
<a name="l00966"></a>00966 computeMinMax(ind, count, i, min_elem, max_elem);
<a name="l00967"></a>00967 span = max_elem - min_elem;
<a name="l00968"></a>00968 <span class="keywordflow">if</span> (span>max_span) {
<a name="l00969"></a>00969 max_span = span;
<a name="l00970"></a>00970 cutfeat = i;
<a name="l00971"></a>00971 cutval = (min_elem+max_elem)/2;
<a name="l00972"></a>00972 }
<a name="l00973"></a>00973 }
<a name="l00974"></a>00974 }
<a name="l00975"></a>00975 <span class="keywordtype">int</span> lim1, lim2;
<a name="l00976"></a>00976 planeSplit(ind, count, cutfeat, cutval, lim1, lim2);
<a name="l00977"></a>00977
<a name="l00978"></a>00978 <span class="keywordflow">if</span> (lim1>count/2) index = lim1;
<a name="l00979"></a>00979 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (lim2<count/2) index = lim2;
<a name="l00980"></a>00980 <span class="keywordflow">else</span> index = count/2;
<a name="l00981"></a>00981 }
<a name="l00982"></a>00982
<a name="l00983"></a>00983
<a name="l00984"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a73b605f0600d237b4b641d5cc2058d84">00984</a> <span class="keywordtype">void</span> middleSplit_(<span class="keywordtype">int</span>* ind, <span class="keywordtype">int</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">count</a>, <span class="keywordtype">int</span>& index, <span class="keywordtype">int</span>& cutfeat, <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">DistanceType</a>& cutval, <span class="keyword">const</span> <a class="code" href="classstd_1_1vector.html">BoundingBox</a>& bbox)
<a name="l00985"></a>00985 {
<a name="l00986"></a>00986 <span class="keyword">const</span> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">DistanceType</a> EPS=<span class="keyword">static_cast<</span><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">DistanceType</a><span class="keyword">></span>(0.00001);
<a name="l00987"></a>00987 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a> max_span = bbox[0].high-bbox[0].low;
<a name="l00988"></a>00988 <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i=1; i<(DIM>0 ? DIM : dim); ++i) {
<a name="l00989"></a>00989 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a> span = bbox[i].high-bbox[i].low;
<a name="l00990"></a>00990 <span class="keywordflow">if</span> (span>max_span) {
<a name="l00991"></a>00991 max_span = span;
<a name="l00992"></a>00992 }
<a name="l00993"></a>00993 }
<a name="l00994"></a>00994 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a> max_spread = -1;
<a name="l00995"></a>00995 cutfeat = 0;
<a name="l00996"></a>00996 <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i=0; i<(DIM>0 ? DIM : dim); ++i) {
<a name="l00997"></a>00997 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a> span = bbox[i].high-bbox[i].low;
<a name="l00998"></a>00998 <span class="keywordflow">if</span> (span>(1-EPS)*max_span) {
<a name="l00999"></a>00999 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a> min_elem, max_elem;
<a name="l01000"></a>01000 computeMinMax(ind, count, cutfeat, min_elem, max_elem);
<a name="l01001"></a>01001 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a> spread = max_elem-min_elem;;
<a name="l01002"></a>01002 <span class="keywordflow">if</span> (spread>max_spread) {
<a name="l01003"></a>01003 cutfeat = i;
<a name="l01004"></a>01004 max_spread = spread;
<a name="l01005"></a>01005 }
<a name="l01006"></a>01006 }
<a name="l01007"></a>01007 }
<a name="l01008"></a>01008 <span class="comment">// split in the middle</span>
<a name="l01009"></a>01009 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">DistanceType</a> split_val = (bbox[cutfeat].low+bbox[cutfeat].high)/2;
<a name="l01010"></a>01010 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a> min_elem, max_elem;
<a name="l01011"></a>01011 computeMinMax(ind, count, cutfeat, min_elem, max_elem);
<a name="l01012"></a>01012
<a name="l01013"></a>01013 <span class="keywordflow">if</span> (split_val<min_elem) cutval = min_elem;
<a name="l01014"></a>01014 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (split_val>max_elem) cutval = max_elem;
<a name="l01015"></a>01015 <span class="keywordflow">else</span> cutval = split_val;
<a name="l01016"></a>01016
<a name="l01017"></a>01017 <span class="keywordtype">int</span> lim1, lim2;
<a name="l01018"></a>01018 planeSplit(ind, count, cutfeat, cutval, lim1, lim2);
<a name="l01019"></a>01019
<a name="l01020"></a>01020 <span class="keywordflow">if</span> (lim1>count/2) index = lim1;
<a name="l01021"></a>01021 <span class="keywordflow">else</span> <span class="keywordflow">if</span> (lim2<count/2) index = lim2;
<a name="l01022"></a>01022 <span class="keywordflow">else</span> index = count/2;
<a name="l01023"></a>01023 }
<a name="l01024"></a>01024
<a name="l01025"></a>01025 <span class="comment"></span>
<a name="l01026"></a>01026 <span class="comment"> /**</span>
<a name="l01027"></a>01027 <span class="comment"> * Subdivide the list of points by a plane perpendicular on axe corresponding</span>
<a name="l01028"></a>01028 <span class="comment"> * to the 'cutfeat' dimension at 'cutval' position.</span>
<a name="l01029"></a>01029 <span class="comment"> *</span>
<a name="l01030"></a>01030 <span class="comment"> * On return:</span>
<a name="l01031"></a>01031 <span class="comment"> * dataset[ind[0..lim1-1]][cutfeat]<cutval</span>
<a name="l01032"></a>01032 <span class="comment"> * dataset[ind[lim1..lim2-1]][cutfeat]==cutval</span>
<a name="l01033"></a>01033 <span class="comment"> * dataset[ind[lim2..count]][cutfeat]>cutval</span>
<a name="l01034"></a>01034 <span class="comment"> */</span>
<a name="l01035"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a7cd481e90c75d1ec49306b2a94c76b44">01035</a> <span class="keywordtype">void</span> planeSplit(<span class="keywordtype">int</span>* ind, <span class="keywordtype">int</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a33da2078a326322a89b0762796b6ccbd">count</a>, <span class="keywordtype">int</span> cutfeat, <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">DistanceType</a> cutval, <span class="keywordtype">int</span>& lim1, <span class="keywordtype">int</span>& lim2)
<a name="l01036"></a>01036 {
<a name="l01037"></a>01037 <span class="comment">/* Move vector indices for left subtree to front of list. */</span>
<a name="l01038"></a>01038 <span class="keywordtype">int</span> left = 0;
<a name="l01039"></a>01039 <span class="keywordtype">int</span> right = count-1;
<a name="l01040"></a>01040 <span class="keywordflow">for</span> (;; ) {
<a name="l01041"></a>01041 <span class="keywordflow">while</span> (left<=right && dataset_get(ind[left],cutfeat)<cutval) ++left;
<a name="l01042"></a>01042 <span class="keywordflow">while</span> (left<=right && dataset_get(ind[right],cutfeat)>=cutval) --right;
<a name="l01043"></a>01043 <span class="keywordflow">if</span> (left>right) <span class="keywordflow">break</span>;
<a name="l01044"></a>01044 std::swap(ind[left], ind[right]);
<a name="l01045"></a>01045 ++left;
<a name="l01046"></a>01046 --right;
<a name="l01047"></a>01047 }
<a name="l01048"></a>01048 <span class="comment">/* If either list is empty, it means that all remaining features</span>
<a name="l01049"></a>01049 <span class="comment"> * are identical. Split in the middle to maintain a balanced tree.</span>
<a name="l01050"></a>01050 <span class="comment"> */</span>
<a name="l01051"></a>01051 lim1 = left;
<a name="l01052"></a>01052 right = count-1;
<a name="l01053"></a>01053 <span class="keywordflow">for</span> (;; ) {
<a name="l01054"></a>01054 <span class="keywordflow">while</span> (left<=right && dataset_get(ind[left],cutfeat)<=cutval) ++left;
<a name="l01055"></a>01055 <span class="keywordflow">while</span> (left<=right && dataset_get(ind[right],cutfeat)>cutval) --right;
<a name="l01056"></a>01056 <span class="keywordflow">if</span> (left>right) <span class="keywordflow">break</span>;
<a name="l01057"></a>01057 std::swap(ind[left], ind[right]);
<a name="l01058"></a>01058 ++left;
<a name="l01059"></a>01059 --right;
<a name="l01060"></a>01060 }
<a name="l01061"></a>01061 lim2 = left;
<a name="l01062"></a>01062 }
<a name="l01063"></a>01063
<a name="l01064"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a652bcb94da37cba34499a63a74a5a8a4">01064</a> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">DistanceType</a> computeInitialDistances(<span class="keyword">const</span> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a>* vec, <a class="code" href="classstd_1_1vector.html" title="STL class.">std::vector<DistanceType></a>& <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a9e5955301b936a6ba02bf179201a0793">dists</a>)<span class="keyword"> const</span>
<a name="l01065"></a>01065 <span class="keyword"> </span>{
<a name="l01066"></a>01066 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">DistanceType</a> distsq = 0.0;
<a name="l01067"></a>01067
<a name="l01068"></a>01068 <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i = 0; i < (DIM>0 ? DIM : dim); ++i) {
<a name="l01069"></a>01069 <span class="keywordflow">if</span> (vec[i] < root_bbox[i].low) {
<a name="l01070"></a>01070 dists[i] = <a class="code" href="group__geometry__grp.html#ga8c0a76e906f12560cfa49fcd269c8398" title="Gets the distance between two points in a 2D space.">distance</a>.accum_dist(vec[i], root_bbox[i].low, i);
<a name="l01071"></a>01071 distsq += dists[i];
<a name="l01072"></a>01072 }
<a name="l01073"></a>01073 <span class="keywordflow">if</span> (vec[i] > root_bbox[i].high) {
<a name="l01074"></a>01074 dists[i] = <a class="code" href="group__geometry__grp.html#ga8c0a76e906f12560cfa49fcd269c8398" title="Gets the distance between two points in a 2D space.">distance</a>.accum_dist(vec[i], root_bbox[i].high, i);
<a name="l01075"></a>01075 distsq += dists[i];
<a name="l01076"></a>01076 }
<a name="l01077"></a>01077 }
<a name="l01078"></a>01078
<a name="l01079"></a>01079 <span class="keywordflow">return</span> distsq;
<a name="l01080"></a>01080 }
<a name="l01081"></a>01081 <span class="comment"></span>
<a name="l01082"></a>01082 <span class="comment"> /**</span>
<a name="l01083"></a>01083 <span class="comment"> * Performs an exact search in the tree starting from a node.</span>
<a name="l01084"></a>01084 <span class="comment"> * \tparam RESULTSET Should be any ResultSet<DistanceType></span>
<a name="l01085"></a>01085 <span class="comment"> */</span>
<a name="l01086"></a>01086 <span class="keyword">template</span> <<span class="keyword">class</span> RESULTSET>
<a name="l01087"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dff098b8369ada2018523d8e2caf7e6">01087</a> <span class="keywordtype">void</span> searchLevel(RESULTSET& result_set, <span class="keyword">const</span> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a>* vec, <span class="keyword">const</span> <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html">NodePtr</a> node, <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">DistanceType</a> mindistsq,
<a name="l01088"></a>01088 <a class="code" href="classstd_1_1vector.html" title="STL class.">std::vector<DistanceType></a>& <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a9e5955301b936a6ba02bf179201a0793">dists</a>, <span class="keyword">const</span> <span class="keywordtype">float</span> epsError, <span class="keywordtype">int</span> &count_leaf)<span class="keyword"> const</span>
<a name="l01089"></a>01089 <span class="keyword"> </span>{
<a name="l01090"></a>01090 <span class="comment">/* If this is a leaf node, then do check and return. */</span>
<a name="l01091"></a>01091 <span class="keywordflow">if</span> ((node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a9f89ac3385c57d8a735a4d9004bf5d6b" title="The child nodes.">child1</a> == NULL)&&(node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#acc45092cb923a11d9317590be29b5dc4">child2</a> == NULL)) {
<a name="l01092"></a>01092 count_leaf += (node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a4af2b70f9aa82818ea759b65e791f8b3">lr</a>.right-node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a4af2b70f9aa82818ea759b65e791f8b3">lr</a>.left);
<a name="l01093"></a>01093 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">DistanceType</a> worst_dist = result_set.worstDist();
<a name="l01094"></a>01094 <span class="keywordflow">for</span> (<span class="keywordtype">int</span> i=node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a4af2b70f9aa82818ea759b65e791f8b3">lr</a>.left; i<node->lr.right; ++i) {
<a name="l01095"></a>01095 <span class="keywordtype">int</span> index = vind[i];<span class="comment">// reorder... : i;</span>
<a name="l01096"></a>01096 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">DistanceType</a> dist = <a class="code" href="group__geometry__grp.html#ga8c0a76e906f12560cfa49fcd269c8398" title="Gets the distance between two points in a 2D space.">distance</a>(vec, index, (DIM>0 ? DIM : dim));
<a name="l01097"></a>01097 <span class="keywordflow">if</span> (dist<worst_dist) {
<a name="l01098"></a>01098 result_set.addPoint(dist,vind[i]);
<a name="l01099"></a>01099 }
<a name="l01100"></a>01100 }
<a name="l01101"></a>01101 <span class="keywordflow">return</span>;
<a name="l01102"></a>01102 }
<a name="l01103"></a>01103
<a name="l01104"></a>01104 <span class="comment">/* Which child branch should be taken first? */</span>
<a name="l01105"></a>01105 <span class="keywordtype">int</span> idx = node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a47fda7bcb8c3237bc347aeac21ad2817">sub</a>.divfeat;
<a name="l01106"></a>01106 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#ad1cbf9b9b733b4cb2a0c94e2263ae6ac">ElementType</a> val = vec[idx];
<a name="l01107"></a>01107 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">DistanceType</a> diff1 = val - node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a47fda7bcb8c3237bc347aeac21ad2817">sub</a>.divlow;
<a name="l01108"></a>01108 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">DistanceType</a> diff2 = val - node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a47fda7bcb8c3237bc347aeac21ad2817">sub</a>.divhigh;
<a name="l01109"></a>01109
<a name="l01110"></a>01110 <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html">NodePtr</a> bestChild;
<a name="l01111"></a>01111 <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html">NodePtr</a> otherChild;
<a name="l01112"></a>01112 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">DistanceType</a> cut_dist;
<a name="l01113"></a>01113 <span class="keywordflow">if</span> ((diff1+diff2)<0) {
<a name="l01114"></a>01114 bestChild = node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a9f89ac3385c57d8a735a4d9004bf5d6b" title="The child nodes.">child1</a>;
<a name="l01115"></a>01115 otherChild = node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#acc45092cb923a11d9317590be29b5dc4">child2</a>;
<a name="l01116"></a>01116 cut_dist = <a class="code" href="group__geometry__grp.html#ga8c0a76e906f12560cfa49fcd269c8398" title="Gets the distance between two points in a 2D space.">distance</a>.accum_dist(val, node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a47fda7bcb8c3237bc347aeac21ad2817">sub</a>.divhigh, idx);
<a name="l01117"></a>01117 }
<a name="l01118"></a>01118 <span class="keywordflow">else</span> {
<a name="l01119"></a>01119 bestChild = node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#acc45092cb923a11d9317590be29b5dc4">child2</a>;
<a name="l01120"></a>01120 otherChild = node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a9f89ac3385c57d8a735a4d9004bf5d6b" title="The child nodes.">child1</a>;
<a name="l01121"></a>01121 cut_dist = <a class="code" href="group__geometry__grp.html#ga8c0a76e906f12560cfa49fcd269c8398" title="Gets the distance between two points in a 2D space.">distance</a>.accum_dist( val, node-><a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_1_1_node.html#a47fda7bcb8c3237bc347aeac21ad2817">sub</a>.divlow, idx);
<a name="l01122"></a>01122 }
<a name="l01123"></a>01123
<a name="l01124"></a>01124 <span class="comment">/* Call recursively to search next level down. */</span>
<a name="l01125"></a>01125 searchLevel(result_set, vec, bestChild, mindistsq, dists, epsError,count_leaf);
<a name="l01126"></a>01126
<a name="l01127"></a>01127 <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a6dc5d921d34570f8f190d4cd1755ae88">DistanceType</a> dst = dists[idx];
<a name="l01128"></a>01128 mindistsq = mindistsq + cut_dist - dst;
<a name="l01129"></a>01129 dists[idx] = cut_dist;
<a name="l01130"></a>01130 <span class="keywordflow">if</span> (mindistsq*epsError<=result_set.worstDist()) {
<a name="l01131"></a>01131 searchLevel(result_set, vec, otherChild, mindistsq, dists, epsError,count_leaf);
<a name="l01132"></a>01132 }
<a name="l01133"></a>01133 dists[idx] = dst;
<a name="l01134"></a>01134 }
<a name="l01135"></a>01135
<a name="l01136"></a>01136
<a name="l01137"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a860fcfd642158e06a47b8b4fe27003fe">01137</a> <span class="keywordtype">void</span> saveIndex(FILE* stream)
<a name="l01138"></a>01138 {
<a name="l01139"></a>01139 <a class="code" href="group__loadsave__grp.html#ga4eb2ec6a057da0c432ddc374800fc6ec">save_value</a>(stream, size_);
<a name="l01140"></a>01140 <a class="code" href="group__loadsave__grp.html#ga4eb2ec6a057da0c432ddc374800fc6ec">save_value</a>(stream, dim);
<a name="l01141"></a>01141 <a class="code" href="group__loadsave__grp.html#ga4eb2ec6a057da0c432ddc374800fc6ec">save_value</a>(stream, root_bbox);
<a name="l01142"></a>01142 <a class="code" href="group__loadsave__grp.html#ga4eb2ec6a057da0c432ddc374800fc6ec">save_value</a>(stream, leaf_max_size_);
<a name="l01143"></a>01143 <a class="code" href="group__loadsave__grp.html#ga4eb2ec6a057da0c432ddc374800fc6ec">save_value</a>(stream, vind);
<a name="l01144"></a>01144 save_tree(stream, root_node);
<a name="l01145"></a>01145 }
<a name="l01146"></a>01146
<a name="l01147"></a><a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html#a1e298a1f4c11a00d6421b2e577e6fe37">01147</a> <span class="keywordtype">void</span> loadIndex(FILE* stream)
<a name="l01148"></a>01148 {
<a name="l01149"></a>01149 <a class="code" href="group__loadsave__grp.html#ga8c271fd91a22446d477ef32aac2dce98">load_value</a>(stream, size_);
<a name="l01150"></a>01150 <a class="code" href="group__loadsave__grp.html#ga8c271fd91a22446d477ef32aac2dce98">load_value</a>(stream, dim);
<a name="l01151"></a>01151 <a class="code" href="group__loadsave__grp.html#ga8c271fd91a22446d477ef32aac2dce98">load_value</a>(stream, root_bbox);
<a name="l01152"></a>01152 <a class="code" href="group__loadsave__grp.html#ga8c271fd91a22446d477ef32aac2dce98">load_value</a>(stream, leaf_max_size_);
<a name="l01153"></a>01153 <a class="code" href="group__loadsave__grp.html#ga8c271fd91a22446d477ef32aac2dce98">load_value</a>(stream, vind);
<a name="l01154"></a>01154 load_tree(stream, root_node);
<a name="l01155"></a>01155 }
<a name="l01156"></a>01156
<a name="l01157"></a>01157 }; <span class="comment">// class KDTree</span>
<a name="l01158"></a>01158
<a name="l01159"></a>01159 <span class="comment"></span>
<a name="l01160"></a>01160 <span class="comment"> /** A simple KD-tree adaptor for working with data directly stored in an Eigen Matrix, without duplicating the data storage.</span>
<a name="l01161"></a>01161 <span class="comment"> * Each row in the matrix represents a point in the state space.</span>
<a name="l01162"></a>01162 <span class="comment"> *</span>
<a name="l01163"></a>01163 <span class="comment"> * Example of usage:</span>
<a name="l01164"></a>01164 <span class="comment"> * \code</span>
<a name="l01165"></a>01165 <span class="comment"> * Eigen::Matrix<num_t,Dynamic,Dynamic> mat;</span>
<a name="l01166"></a>01166 <span class="comment"> * // Fill out "mat"...</span>
<a name="l01167"></a>01167 <span class="comment"> *</span>
<a name="l01168"></a>01168 <span class="comment"> * typedef KDTreeEigenMatrixAdaptor< Eigen::Matrix<num_t,Dynamic,Dynamic> > my_kd_tree_t;</span>
<a name="l01169"></a>01169 <span class="comment"> * const int max_leaf = 10;</span>
<a name="l01170"></a>01170 <span class="comment"> * my_kd_tree_t mat_index(dimdim, mat, max_leaf );</span>
<a name="l01171"></a>01171 <span class="comment"> * mat_index.index->buildIndex();</span>
<a name="l01172"></a>01172 <span class="comment"> * mat_index.index->...</span>
<a name="l01173"></a>01173 <span class="comment"> * \endcode</span>
<a name="l01174"></a>01174 <span class="comment"> *</span>
<a name="l01175"></a>01175 <span class="comment"> * \tparam DIM If set to >0, it specifies a compile-time fixed dimensionality for the points in the data set, allowing more compiler optimizations.</span>
<a name="l01176"></a>01176 <span class="comment"> * \tparam Distance The distance metric to use: nanoflann::metric_L1, nanoflann::metric_L2, nanoflann::metric_L2_Simple, etc.</span>
<a name="l01177"></a>01177 <span class="comment"> */</span>
<a name="l01178"></a>01178 <span class="keyword">template</span> <<span class="keyword">class </span>MatrixType, <span class="keywordtype">int</span> DIM = -1, <span class="keyword">class </span>Distance = nanoflann::metric_L2>
<a name="l01179"></a>01179 <span class="keyword">struct </span>KDTreeEigenMatrixAdaptor
<a name="l01180"></a>01180 {
<a name="l01181"></a><a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#ae42b88f3f0d79ca079d18b393f65b3de">01181</a> <span class="keyword">typedef</span> <a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html" title="A simple KD-tree adaptor for working with data directly stored in an Eigen Matrix, without duplicating the data storage.">KDTreeEigenMatrixAdaptor<MatrixType,DIM,Distance></a> <a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#ae42b88f3f0d79ca079d18b393f65b3de">self_t</a>;
<a name="l01182"></a><a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#ab1cad69805da71d5a70f2d85396c3eb1">01182</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> MatrixType::Scalar <a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#ab1cad69805da71d5a70f2d85396c3eb1">num_t</a>;
<a name="l01183"></a><a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#a19dd598e6e3a292e10bfbfe8c0701c33">01183</a> <span class="keyword">typedef</span> <span class="keyword">typename</span> Distance::template traits<num_t,self_t>::distance_t <a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#a19dd598e6e3a292e10bfbfe8c0701c33">metric_t</a>;
<a name="l01184"></a><a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#a24f687eb77bab6208e889d2d53986884">01184</a> <span class="keyword">typedef</span> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html" title="kd-tree index">KDTreeSingleIndexAdaptor< metric_t,self_t,DIM></a> <a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#a24f687eb77bab6208e889d2d53986884">index_t</a>;
<a name="l01185"></a>01185
<a name="l01186"></a><a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#a8a614b7503f9fc363e233502b85fc6aa">01186</a> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html" title="kd-tree index">index_t</a>* <a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#a8a614b7503f9fc363e233502b85fc6aa">index</a>; <span class="comment">//! The kd-tree index for the user to call its methods as usual with any other FLANN index.</span>
<a name="l01187"></a>01187 <span class="comment"></span><span class="comment"></span>
<a name="l01188"></a>01188 <span class="comment"> /// Constructor: takes a const ref to the matrix object with the data points</span>
<a name="l01189"></a><a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#a4beb5e235210c02df914bba5079553f8">01189</a> <span class="comment"></span> <a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html" title="A simple KD-tree adaptor for working with data directly stored in an Eigen Matrix, without duplicating the data storage.">KDTreeEigenMatrixAdaptor</a>(<span class="keyword">const</span> <span class="keywordtype">int</span> dimensionality, <span class="keyword">const</span> MatrixType &mat, <span class="keyword">const</span> <span class="keywordtype">int</span> leaf_max_size = 10) : m_data_matrix(mat)
<a name="l01190"></a>01190 {
<a name="l01191"></a>01191 <span class="keyword">const</span> <span class="keywordtype">size_t</span> dims = mat.cols();
<a name="l01192"></a>01192 <span class="keywordflow">if</span> (DIM>0 && static_cast<int>(dims)!=DIM)
<a name="l01193"></a>01193 <span class="keywordflow">throw</span> <a class="code" href="classstd_1_1runtime__error.html" title="STL class.">std::runtime_error</a>(<span class="stringliteral">"Data set dimensionality does not match the 'DIM' template argument"</span>);
<a name="l01194"></a>01194 index = <span class="keyword">new</span> <a class="code" href="classnanoflann_1_1_k_d_tree_single_index_adaptor.html" title="kd-tree index">index_t</a>( dims, *<span class="keyword">this</span> <span class="comment">/* adaptor */</span>, <a class="code" href="structnanoflann_1_1_k_d_tree_single_index_adaptor_params.html" title="Parameters.">nanoflann::KDTreeSingleIndexAdaptorParams</a>(leaf_max_size, dims ) );
<a name="l01195"></a>01195 index->buildIndex();
<a name="l01196"></a>01196 }
<a name="l01197"></a>01197
<a name="l01198"></a><a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#af26265a7979715e29c69b1400330b77e">01198</a> <a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#af26265a7979715e29c69b1400330b77e">~KDTreeEigenMatrixAdaptor</a>() {
<a name="l01199"></a>01199 <span class="keyword">delete</span> index;
<a name="l01200"></a>01200 }
<a name="l01201"></a>01201
<a name="l01202"></a><a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#a5f6ac097ba1aaf0d74e8c0c894da3cbd">01202</a> <span class="keyword">const</span> MatrixType &<a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#a5f6ac097ba1aaf0d74e8c0c894da3cbd">m_data_matrix</a>;
<a name="l01203"></a>01203 <span class="comment"></span>
<a name="l01204"></a>01204 <span class="comment"> /** Query for the \a num_closest closest points to a given point (entered as query_point[0:dim-1]).</span>
<a name="l01205"></a>01205 <span class="comment"> * Note that this is a short-cut method for index->findNeighbors().</span>
<a name="l01206"></a>01206 <span class="comment"> * The user can also call index->... methods as desired.</span>
<a name="l01207"></a>01207 <span class="comment"> */</span>
<a name="l01208"></a><a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#a97a6956323ec124949d8389d034f07c9">01208</a> <span class="keyword">inline</span> <span class="keywordtype">void</span> query(<span class="keyword">const</span> <a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#ab1cad69805da71d5a70f2d85396c3eb1">num_t</a> *query_point, <span class="keywordtype">int</span> num_closest, <span class="keywordtype">int</span> *out_indices, <a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#ab1cad69805da71d5a70f2d85396c3eb1">num_t</a> *out_distances_sq, <span class="keyword">const</span> <span class="keywordtype">int</span> nChecks = 10)<span class="keyword"> const</span>
<a name="l01209"></a>01209 <span class="keyword"> </span>{
<a name="l01210"></a>01210 nanoflann<a class="code" href="classnanoflann_1_1_k_n_n_result_set.html">::KNNResultSet<typename MatrixType::Scalar></a> resultSet(num_closest);
<a name="l01211"></a>01211 resultSet.<a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a4fefecb0ff9480ceeb1212afa67f9966">init</a>(out_indices, out_distances_sq);
<a name="l01212"></a>01212 index->findNeighbors(resultSet, query_point, <a class="code" href="structnanoflann_1_1_search_params.html" title="Search options for KDTreeSingleIndexAdaptor::findNeighbors()">nanoflann::SearchParams</a>(nChecks));
<a name="l01213"></a>01213 }
<a name="l01214"></a>01214 <span class="comment"></span>
<a name="l01215"></a>01215 <span class="comment"> /** @name Interface expected by KDTreeSingleIndexAdaptor</span>
<a name="l01216"></a>01216 <span class="comment"> * @{ */</span>
<a name="l01217"></a>01217
<a name="l01218"></a><a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#a93c2e730f59ea059aa84453c3087c81d">01218</a> <span class="keyword">const</span> <a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html" title="A simple KD-tree adaptor for working with data directly stored in an Eigen Matrix, without duplicating the data storage.">self_t</a> & <a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#a93c2e730f59ea059aa84453c3087c81d">derived</a>()<span class="keyword"> const </span>{
<a name="l01219"></a>01219 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l01220"></a>01220 }
<a name="l01221"></a><a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#af5a0b19d1c51eab7a5347788caa6cabd">01221</a> <a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html" title="A simple KD-tree adaptor for working with data directly stored in an Eigen Matrix, without duplicating the data storage.">self_t</a> & <a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#af5a0b19d1c51eab7a5347788caa6cabd">derived</a>() {
<a name="l01222"></a>01222 <span class="keywordflow">return</span> *<span class="keyword">this</span>;
<a name="l01223"></a>01223 }
<a name="l01224"></a>01224
<a name="l01225"></a>01225 <span class="comment">// Must return the number of data points</span>
<a name="l01226"></a><a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#a562c7c493192bdf91852c0c5ed961659">01226</a> <span class="keyword">inline</span> <span class="keywordtype">size_t</span> <a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#a562c7c493192bdf91852c0c5ed961659">kdtree_get_point_count</a>()<span class="keyword"> const </span>{
<a name="l01227"></a>01227 <span class="keywordflow">return</span> m_data_matrix.rows();
<a name="l01228"></a>01228 }
<a name="l01229"></a>01229
<a name="l01230"></a>01230 <span class="comment">// Returns the distance between the vector "p1[0:size-1]" and the data point with index "idx_p2" stored in the class:</span>
<a name="l01231"></a><a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#adf8861cb543e85f8e1cdb5ef8c6ea41f">01231</a> <span class="keyword">inline</span> <a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#ab1cad69805da71d5a70f2d85396c3eb1">num_t</a> kdtree_distance(<span class="keyword">const</span> <a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#ab1cad69805da71d5a70f2d85396c3eb1">num_t</a> *p1, <span class="keyword">const</span> <span class="keywordtype">size_t</span> idx_p2,<span class="keywordtype">size_t</span> <a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a1ccd37d4307264f3c70abb55dc5d57e1">size</a>)<span class="keyword"> const</span>
<a name="l01232"></a>01232 <span class="keyword"> </span>{
<a name="l01233"></a>01233 <a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#ab1cad69805da71d5a70f2d85396c3eb1">num_t</a> s=0;
<a name="l01234"></a>01234 <span class="keywordflow">for</span> (<span class="keywordtype">size_t</span> i=0; i<<a class="code" href="classnanoflann_1_1_k_n_n_result_set.html#a1ccd37d4307264f3c70abb55dc5d57e1">size</a>; i++) {
<a name="l01235"></a>01235 <span class="keyword">const</span> <a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#ab1cad69805da71d5a70f2d85396c3eb1">num_t</a> d= p1[i]-m_data_matrix.coeff(idx_p2,i);
<a name="l01236"></a>01236 s+=d*d;
<a name="l01237"></a>01237 }
<a name="l01238"></a>01238 <span class="keywordflow">return</span> s;
<a name="l01239"></a>01239 }
<a name="l01240"></a>01240
<a name="l01241"></a>01241 <span class="comment">// Returns the dim'th component of the idx'th point in the class:</span>
<a name="l01242"></a><a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#a4e0111c5f1da2a5539b601b4cbc77b15">01242</a> <span class="keyword">inline</span> <a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#ab1cad69805da71d5a70f2d85396c3eb1">num_t</a> <a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#a4e0111c5f1da2a5539b601b4cbc77b15">kdtree_get_pt</a>(<span class="keyword">const</span> <span class="keywordtype">size_t</span> idx, <span class="keywordtype">int</span> dim)<span class="keyword"> const </span>{
<a name="l01243"></a>01243 <span class="keywordflow">return</span> m_data_matrix.coeff(idx,dim);
<a name="l01244"></a>01244 }
<a name="l01245"></a>01245
<a name="l01246"></a>01246 <span class="comment">// Optional bounding-box computation: return false to default to a standard bbox computation loop.</span>
<a name="l01247"></a>01247 <span class="comment">// Return true if the BBOX was already computed by the class and returned in "bb" so it can be avoided to redo it again.</span>
<a name="l01248"></a>01248 <span class="comment">// Look at bb.size() to find out the expected dimensionality (e.g. 2 or 3 for point clouds)</span>
<a name="l01249"></a>01249 <span class="keyword">template</span> <<span class="keyword">class</span> BBOX>
<a name="l01250"></a><a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#aab6300e6075e62c40a9fcbbbd4eaf898">01250</a> <span class="keywordtype">bool</span> <a class="code" href="structnanoflann_1_1_k_d_tree_eigen_matrix_adaptor.html#aab6300e6075e62c40a9fcbbbd4eaf898">kdtree_get_bbox</a>(BBOX &bb)<span class="keyword"> const </span>{
<a name="l01251"></a>01251 <span class="keywordflow">return</span> <span class="keyword">false</span>;
<a name="l01252"></a>01252 }
<a name="l01253"></a>01253 <span class="comment"></span>
<a name="l01254"></a>01254 <span class="comment"> /** @} */</span>
<a name="l01255"></a>01255
<a name="l01256"></a>01256 }; <span class="comment">// end of KDTreeEigenMatrixAdaptor</span><span class="comment"></span>
<a name="l01257"></a>01257 <span class="comment"> /** @} */</span>
<a name="l01258"></a>01258 <span class="comment"></span>
<a name="l01259"></a>01259 <span class="comment">/** @} */</span> <span class="comment">// end of grouping</span>
<a name="l01260"></a>01260 } <span class="comment">// end of NS</span>
<a name="l01261"></a>01261
<a name="l01262"></a>01262
<a name="l01263"></a>01263 <span class="preprocessor">#endif </span><span class="comment">/* NANOFLANN_HPP_ */</span>
</pre></div></div>
</div>
<br><hr><br> <table border="0" width="100%"> <tr> <td> Page generated by <a href="http://www.doxygen.org" target="_blank">Doxygen 1.7.5</a> for MRPT 0.9.5 SVN: at Sun Sep 25 17:20:18 UTC 2011</td><td></td> <td width="100"> </td> <td width="150"> </td></tr> </table> </body></html>
