1%%%%%%%%%%%%%%%%%%% 2% XLiFE++ is an extended library of finite elements written in C++ 3% Copyright (C) 2014 Lunéville, Eric; Kielbasiewicz, Nicolas; Lafranche, Yvon; Nguyen, Manh-Ha; Chambeyron, Colin 4% 5% This program is free software: you can redistribute it and/or modify 6% it under the terms of the GNU General Public License as published by 7% the Free Software Foundation, either version 3 of the License, or 8% (at your option) any later version. 9% This program is distributed in the hope that it will be useful, 10% but WITHOUT ANY WARRANTY; without even the implied warranty of 11% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12% GNU General Public License for more details. 13% You should have received a copy of the GNU General Public License 14% along with this program. If not, see <http://www.gnu.org/licenses/>. 15%%%%%%%%%%%%%%%%%%% 16 17\section{The {\classtitle KdTree} class} 18 19The {\class KdTree} class implements the well known kdtree which is a binary tree where objects are separated using component by component separation. Usually objects are points but the following implementation is templated to deal with any class T that have components that can be separated. More precisely, the T class has to provide the following: 20\vspace{.1cm} 21\begin{lstlisting}[]{} 22T::SepValueType; 23T::operator()(int); 24T::dim(); 25int Tcompare(const T& t, int c, const T::SepValueType& s); 26//return -1 (t_c<s), 1 (t_c>s) or 0 (t_c=s) 27int maxSeparator(const T& t1, const T& tT2, int &c, T::SepValueType& s); 28// find the component index c where separation is maximal, update s as the middle value and return the comparison of t1 and t2 (1,-1,0) 29\end{lstlisting} 30\vspace{.3cm} 31Such tree may find the nearest object of a given object in a fast way ($n\log\,n$ in the most cases and $n$ in worst cases).\\ 32 33The {\class KdTree} class is based on the {\class KdNode} class which is in fact the main class, {\class KdTree} handling the root node. A {\class KdNode} is either a separation line (component that separates two points and value of separation) or a terminal leaf containing a separated object. 34 35\subsection*{{\classtitle KdNode} class} 36 37\vspace{.1cm} 38\begin{lstlisting}[]{} 39template <class T> 40class KdNode 41{ 42private : 43 typedef typename T::SepValueType SvType; 44 KdNode * parent_; //!< pointer to parent node 45 KdNode * left_; //!< pointer to left node 46 KdNode * right_; //!< pointer to right node 47 const T * obj_; //!< object pointer linked to node 48 int separator_; //!< separation component 49 SvType sv_; //!< separation value 50} 51\end{lstlisting} 52\vspace{.3cm} 53It has two basic constructors, a destructor and a node insertion function 54\vspace{.1cm} 55\begin{lstlisting}[]{} 56KdNode(); 57KdNode(const T *O,int s, KdNode * p); 58~KdNode(); 59void insert(const T *); 60\end{lstlisting} 61\vspace{.3cm} 62The {\cmd insert} function is the fundamental function used in building of kdtree : it travels in tree up to find a free box containing the object to be inserted; if no free box is found, the last non empty box containing object to be inserted and an other object is split in two boxes. The tree obtained by this method has not an optimal balancing ! 63\begin{figure}[H] 64\centering 65\includePict[width=8cm]{kdtree.pdf} 66\caption{exemple of separation of 2d points} 67\end{figure} 68The class provides some utitilities 69\vspace{.1cm} 70\begin{lstlisting}[]{} 71Number& depth(Number &) const; //!< return node depth 72void print(std::ostream&, std::string &) const; 73void printBoxes(std::ostream &os, Box<SvType> b) const; 74template <class S> 75friend std::ostream& operator<<(std::ostream& os,const KdNode<S> & node); 76\end{lstlisting} 77\vspace{.3cm} 78and the important function to search the nearest object of a given object: 79\vspace{.1cm} 80\begin{lstlisting}[]{} 81void searchNearest(const T *, const T *&, SvType &); 82\end{lstlisting} 83\vspace{.3cm} 84\begin{figure}[H] 85\centering 86\includePict[width=8cm]{kdtree_search.pdf} 87\end{figure} 88 89\subsection*{{\classtitle KdTree} class} 90 91As already mentioned {\class KdTree} handles the root node of tree and mainly encapsulated the {\class KdNode} functions 92\vspace{.1cm} 93\begin{lstlisting}[]{} 94template <class T> 95class KdTree 96{ 97private : 98 typedef typename T::SepValueType SvType; //separator value type 99 KdNode<T>* root; //rootnode of the tree 100 Dimen dimT; //object dimension 101 } 102\end{lstlisting} 103\vspace{.3cm} 104\vspace{.1cm} 105\begin{lstlisting}[]{} 106KdTree() {root=new KdNode<T>();dimT=0;} 107KdTree(const std::vector<T>&); 108~KdTree() {delete root;}; 109bool isVoid() const; 110Dimen dim() const; 111void insert(const T&); 112void insert(const std::vector<T>&); 113Number depth() const; 114const T* searchNearest(const T &) const; 115void print(std::ostream& out) const; 116template <typename R> 117 void printBoxes(std::ostream &os, const Box<R>& rb); 118template <typename R> 119 void printBoxes(const std::string& file, const Box<R>& rb); 120template <class S> 121 friend std::ostream& operator<<(std::ostream& os,const KdTree<S>& node); 122\end{lstlisting} 123\vspace{.3cm} 124\displayInfos{library=utils, header=KdTree.hpp, implementation=KdTree.hpp, 125test=test\_KdTree.cpp, header dep={space.h, config.h, utils.h}} 126