aboutsummaryrefslogblamecommitdiffstats
path: root/doc/latex/classmeow_1_1KD__Tree.tex
blob: 2c2f010a96177eefd5f587c448f1256c29c5466f (plain) (tree)
















































                                                                                                                                                                                                                                                                            
                                                  


                   
                                                                                                                                                                                                   






                                                                                                                                                                                                                            







                                                                                                                                      



                                                   









                                                                                                                                                                                                                                                                                               



                                                    











                                                                                                                                                                                                          



                                                    










                                                                                                                                                                                                          



                                                    












                                                                                                                                                                                                                        



                                                    











                                                                                                                                                                                   



                                                    










                                                                                                                                                                                   



                                                    










                                                                                                                                                                                   



                                                    










                                                                                                                                                                                                 



                                                    










                                                                                                                                                                                     



                                                    












                                                                                                                                                                                            




                                                                                                                                                                                                                                                                                                       











                                                                                                                                                                                   



                                                    


                                                                                                   
\hypertarget{classmeow_1_1KD__Tree}{\section{meow\-:\-:K\-D\-\_\-\-Tree$<$ Vector, Scalar $>$ Class Template Reference}
\label{classmeow_1_1KD__Tree}\index{meow\-::\-K\-D\-\_\-\-Tree$<$ Vector, Scalar $>$@{meow\-::\-K\-D\-\_\-\-Tree$<$ Vector, Scalar $>$}}
}


{\ttfamily k-\/dimension} tree  




{\ttfamily \#include \char`\"{}K\-D\-\_\-\-Tree.\-h\char`\"{}}

\subsection*{Public Types}
\begin{DoxyCompactItemize}
\item 
typedef std\-::vector$<$ \hyperlink{classmeow_1_1Vector}{Vector} $>$ \hyperlink{classmeow_1_1KD__Tree_afc143e90dba569c51b6eb146ba9df7f8}{Vectors}
\begin{DoxyCompactList}\small\item\em Custom Type\-: Vectors is {\ttfamily std\-::vector$<$\-Vector$>$} \end{DoxyCompactList}\end{DoxyCompactItemize}
\subsection*{Public Member Functions}
\begin{DoxyCompactItemize}
\item 
\hyperlink{classmeow_1_1KD__Tree_a782840070cd90370c37d72e8a39765f9}{K\-D\-\_\-\-Tree} ()
\begin{DoxyCompactList}\small\item\em constructor, with dimension = 1 \end{DoxyCompactList}\item 
\hyperlink{classmeow_1_1KD__Tree_aafecfa34e96615249e11e9ba1b85fdc7}{K\-D\-\_\-\-Tree} (size\-\_\-t dimension)
\begin{DoxyCompactList}\small\item\em constructor, given dimension \end{DoxyCompactList}\item 
\hyperlink{classmeow_1_1KD__Tree_a6ffacb6d4020cfb1c127b68f3f427ee4}{$\sim$\-K\-D\-\_\-\-Tree} ()
\begin{DoxyCompactList}\small\item\em destructor \end{DoxyCompactList}\item 
void \hyperlink{classmeow_1_1KD__Tree_ad1af6def42b23b9b4acef03d32774b9e}{insert} (\hyperlink{classmeow_1_1Vector}{Vector} const \&v)
\begin{DoxyCompactList}\small\item\em 將給定的\-Vector加到set中 \end{DoxyCompactList}\item 
bool \hyperlink{classmeow_1_1KD__Tree_adb0aaa5a70a7255935d8a4326c454434}{erase} (\hyperlink{classmeow_1_1Vector}{Vector} const \&v)
\begin{DoxyCompactList}\small\item\em 將給定的\-Vector從set移除 \end{DoxyCompactList}\item 
void \hyperlink{classmeow_1_1KD__Tree_abdeb11a064dc06f80437126d6744b022}{build} ()
\begin{DoxyCompactList}\small\item\em 檢查至今是否有 insert/erase 被呼叫來決定是否 {\ttfamily rebuild()} \end{DoxyCompactList}\item 
void \hyperlink{classmeow_1_1KD__Tree_a09bf16356618fde6d256a843b87f44b6}{force\-Build} ()
\begin{DoxyCompactList}\small\item\em 重新建樹 \end{DoxyCompactList}\item 
\hyperlink{classmeow_1_1KD__Tree_afc143e90dba569c51b6eb146ba9df7f8}{Vectors} \hyperlink{classmeow_1_1KD__Tree_a10e1cac9c14e047d77fb95eaf0b49bd8}{query} (\hyperlink{classmeow_1_1Vector}{Vector} const \&v, size\-\_\-t nearest\-Number, bool compare\-Whole\-Vector) const 
\begin{DoxyCompactList}\small\item\em 查找 \end{DoxyCompactList}\item 
void \hyperlink{classmeow_1_1KD__Tree_a586afb8e59665a951ab0a9deae2fde40}{clear} ()
\begin{DoxyCompactList}\small\item\em 清空所有資料 \end{DoxyCompactList}\item 
void \hyperlink{classmeow_1_1KD__Tree_a45be7cf06442b1a75902faa266950121}{reset} (size\-\_\-t dimension)
\begin{DoxyCompactList}\small\item\em 清空所有資料並重新給定維度 \end{DoxyCompactList}\end{DoxyCompactItemize}


\subsection{Detailed Description}
\subsubsection*{template$<$class Vector, class Scalar$>$class meow\-::\-K\-D\-\_\-\-Tree$<$ Vector, Scalar $>$}

{\ttfamily k-\/dimension} tree 

全名k-\/dimension tree, 用來維護由{\bfseries N個\-K維度向量所成的集合}, 並可於該set中查找 {\bfseries 前i個離給定向量最接近的向量} 

\subsubsection*{Template Class Operators Request }

\begin{TabularC}{6}
\hline
\rowcolor{lightgray}\PBS\raggedleft {\bf const?}&\PBS\centering {\bf Typename}&\PBS\raggedleft {\bf Operator }&{\bf Parameters }&\PBS\centering {\bf Return Type }&{\bf Description  }\\\cline{1-6}
\PBS\raggedleft const &\PBS\centering \hyperlink{classmeow_1_1Vector}{Vector} &\PBS\raggedleft operator\mbox{[}\mbox{]} &(size\-\_\-t {\ttfamily n}) &\PBS\centering Scalar &取得第 {\ttfamily n} 維度量 \\\cline{1-6}
\PBS\raggedleft const &\PBS\centering \hyperlink{classmeow_1_1Vector}{Vector} &\PBS\raggedleft operator$<$ &(\hyperlink{classmeow_1_1Vector}{Vector} {\ttfamily v}) &\PBS\centering bool &權重比較 \\\cline{1-6}
\PBS\raggedleft const &\PBS\centering Scalar &\PBS\raggedleft operator$\ast$ &(Scalar {\ttfamily s}) &\PBS\centering Scalar &相乘 \\\cline{1-6}
\PBS\raggedleft const &\PBS\centering Scalar &\PBS\raggedleft operator+ &(Scalar {\ttfamily s}) &\PBS\centering Scalar &相加 \\\cline{1-6}
\PBS\raggedleft const &\PBS\centering Scalar &\PBS\raggedleft operator-\/ &(Scalar {\ttfamily s}) &\PBS\centering Scalar &相差 \\\cline{1-6}
\PBS\raggedleft const &\PBS\centering Scalar &\PBS\raggedleft operator$<$ &(Scalar {\ttfamily s}) &\PBS\centering bool &大小比較 \\\cline{1-6}
\end{TabularC}
\begin{DoxyNote}{Note}
\-: 此資料結構只有在 N $>$$>$ 2 $^{\mbox{K}}$  時才比較有優勢, 當 K 逐漸變大時, 所花時間會跟暴搜沒兩樣
\end{DoxyNote}
\begin{DoxyAuthor}{Author}
cat\-\_\-leopard 
\end{DoxyAuthor}


Definition at line 40 of file K\-D\-\_\-\-Tree.\-h.



\subsection{Member Typedef Documentation}
\hypertarget{classmeow_1_1KD__Tree_afc143e90dba569c51b6eb146ba9df7f8}{\index{meow\-::\-K\-D\-\_\-\-Tree@{meow\-::\-K\-D\-\_\-\-Tree}!Vectors@{Vectors}}
\index{Vectors@{Vectors}!meow::KD_Tree@{meow\-::\-K\-D\-\_\-\-Tree}}
\subsubsection[{Vectors}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Vector , class Scalar $>$ typedef std\-::vector$<${\bf Vector}$>$ {\bf meow\-::\-K\-D\-\_\-\-Tree}$<$ {\bf Vector}, Scalar $>$\-::{\bf Vectors}}}\label{classmeow_1_1KD__Tree_afc143e90dba569c51b6eb146ba9df7f8}


Custom Type\-: Vectors is {\ttfamily std\-::vector$<$\-Vector$>$} 



Definition at line 189 of file K\-D\-\_\-\-Tree.\-h.



\subsection{Constructor \& Destructor Documentation}
\hypertarget{classmeow_1_1KD__Tree_a782840070cd90370c37d72e8a39765f9}{\index{meow\-::\-K\-D\-\_\-\-Tree@{meow\-::\-K\-D\-\_\-\-Tree}!K\-D\-\_\-\-Tree@{K\-D\-\_\-\-Tree}}
\index{K\-D\-\_\-\-Tree@{K\-D\-\_\-\-Tree}!meow::KD_Tree@{meow\-::\-K\-D\-\_\-\-Tree}}
\subsubsection[{K\-D\-\_\-\-Tree}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Vector , class Scalar $>$ {\bf meow\-::\-K\-D\-\_\-\-Tree}$<$ {\bf Vector}, Scalar $>$\-::{\bf K\-D\-\_\-\-Tree} (
\begin{DoxyParamCaption}
{}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1KD__Tree_a782840070cd90370c37d72e8a39765f9}


constructor, with dimension = 1 



Definition at line 192 of file K\-D\-\_\-\-Tree.\-h.

\hypertarget{classmeow_1_1KD__Tree_aafecfa34e96615249e11e9ba1b85fdc7}{\index{meow\-::\-K\-D\-\_\-\-Tree@{meow\-::\-K\-D\-\_\-\-Tree}!K\-D\-\_\-\-Tree@{K\-D\-\_\-\-Tree}}
\index{K\-D\-\_\-\-Tree@{K\-D\-\_\-\-Tree}!meow::KD_Tree@{meow\-::\-K\-D\-\_\-\-Tree}}
\subsubsection[{K\-D\-\_\-\-Tree}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Vector , class Scalar $>$ {\bf meow\-::\-K\-D\-\_\-\-Tree}$<$ {\bf Vector}, Scalar $>$\-::{\bf K\-D\-\_\-\-Tree} (
\begin{DoxyParamCaption}
\item[{size\-\_\-t}]{dimension}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1KD__Tree_aafecfa34e96615249e11e9ba1b85fdc7}


constructor, given dimension 



Definition at line 196 of file K\-D\-\_\-\-Tree.\-h.

\hypertarget{classmeow_1_1KD__Tree_a6ffacb6d4020cfb1c127b68f3f427ee4}{\index{meow\-::\-K\-D\-\_\-\-Tree@{meow\-::\-K\-D\-\_\-\-Tree}!$\sim$\-K\-D\-\_\-\-Tree@{$\sim$\-K\-D\-\_\-\-Tree}}
\index{$\sim$\-K\-D\-\_\-\-Tree@{$\sim$\-K\-D\-\_\-\-Tree}!meow::KD_Tree@{meow\-::\-K\-D\-\_\-\-Tree}}
\subsubsection[{$\sim$\-K\-D\-\_\-\-Tree}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Vector , class Scalar $>$ {\bf meow\-::\-K\-D\-\_\-\-Tree}$<$ {\bf Vector}, Scalar $>$\-::$\sim${\bf K\-D\-\_\-\-Tree} (
\begin{DoxyParamCaption}
{}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1KD__Tree_a6ffacb6d4020cfb1c127b68f3f427ee4}


destructor 



Definition at line 201 of file K\-D\-\_\-\-Tree.\-h.



\subsection{Member Function Documentation}
\hypertarget{classmeow_1_1KD__Tree_abdeb11a064dc06f80437126d6744b022}{\index{meow\-::\-K\-D\-\_\-\-Tree@{meow\-::\-K\-D\-\_\-\-Tree}!build@{build}}
\index{build@{build}!meow::KD_Tree@{meow\-::\-K\-D\-\_\-\-Tree}}
\subsubsection[{build}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Vector , class Scalar $>$ void {\bf meow\-::\-K\-D\-\_\-\-Tree}$<$ {\bf Vector}, Scalar $>$\-::build (
\begin{DoxyParamCaption}
{}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1KD__Tree_abdeb11a064dc06f80437126d6744b022}


檢查至今是否有 insert/erase 被呼叫來決定是否 {\ttfamily rebuild()} 



Definition at line 231 of file K\-D\-\_\-\-Tree.\-h.

\hypertarget{classmeow_1_1KD__Tree_a586afb8e59665a951ab0a9deae2fde40}{\index{meow\-::\-K\-D\-\_\-\-Tree@{meow\-::\-K\-D\-\_\-\-Tree}!clear@{clear}}
\index{clear@{clear}!meow::KD_Tree@{meow\-::\-K\-D\-\_\-\-Tree}}
\subsubsection[{clear}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Vector , class Scalar $>$ void {\bf meow\-::\-K\-D\-\_\-\-Tree}$<$ {\bf Vector}, Scalar $>$\-::clear (
\begin{DoxyParamCaption}
{}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1KD__Tree_a586afb8e59665a951ab0a9deae2fde40}


清空所有資料 



Definition at line 286 of file K\-D\-\_\-\-Tree.\-h.

\hypertarget{classmeow_1_1KD__Tree_adb0aaa5a70a7255935d8a4326c454434}{\index{meow\-::\-K\-D\-\_\-\-Tree@{meow\-::\-K\-D\-\_\-\-Tree}!erase@{erase}}
\index{erase@{erase}!meow::KD_Tree@{meow\-::\-K\-D\-\_\-\-Tree}}
\subsubsection[{erase}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Vector , class Scalar $>$ bool {\bf meow\-::\-K\-D\-\_\-\-Tree}$<$ {\bf Vector}, Scalar $>$\-::erase (
\begin{DoxyParamCaption}
\item[{{\bf Vector} const \&}]{v}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1KD__Tree_adb0aaa5a70a7255935d8a4326c454434}


將給定的\-Vector從set移除 



Definition at line 215 of file K\-D\-\_\-\-Tree.\-h.

\hypertarget{classmeow_1_1KD__Tree_a09bf16356618fde6d256a843b87f44b6}{\index{meow\-::\-K\-D\-\_\-\-Tree@{meow\-::\-K\-D\-\_\-\-Tree}!force\-Build@{force\-Build}}
\index{force\-Build@{force\-Build}!meow::KD_Tree@{meow\-::\-K\-D\-\_\-\-Tree}}
\subsubsection[{force\-Build}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Vector , class Scalar $>$ void {\bf meow\-::\-K\-D\-\_\-\-Tree}$<$ {\bf Vector}, Scalar $>$\-::force\-Build (
\begin{DoxyParamCaption}
{}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1KD__Tree_a09bf16356618fde6d256a843b87f44b6}


重新建樹 



Definition at line 240 of file K\-D\-\_\-\-Tree.\-h.

\hypertarget{classmeow_1_1KD__Tree_ad1af6def42b23b9b4acef03d32774b9e}{\index{meow\-::\-K\-D\-\_\-\-Tree@{meow\-::\-K\-D\-\_\-\-Tree}!insert@{insert}}
\index{insert@{insert}!meow::KD_Tree@{meow\-::\-K\-D\-\_\-\-Tree}}
\subsubsection[{insert}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Vector , class Scalar $>$ void {\bf meow\-::\-K\-D\-\_\-\-Tree}$<$ {\bf Vector}, Scalar $>$\-::insert (
\begin{DoxyParamCaption}
\item[{{\bf Vector} const \&}]{v}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1KD__Tree_ad1af6def42b23b9b4acef03d32774b9e}


將給定的\-Vector加到set中 



Definition at line 207 of file K\-D\-\_\-\-Tree.\-h.

\hypertarget{classmeow_1_1KD__Tree_a10e1cac9c14e047d77fb95eaf0b49bd8}{\index{meow\-::\-K\-D\-\_\-\-Tree@{meow\-::\-K\-D\-\_\-\-Tree}!query@{query}}
\index{query@{query}!meow::KD_Tree@{meow\-::\-K\-D\-\_\-\-Tree}}
\subsubsection[{query}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Vector , class Scalar $>$ {\bf Vectors} {\bf meow\-::\-K\-D\-\_\-\-Tree}$<$ {\bf Vector}, Scalar $>$\-::query (
\begin{DoxyParamCaption}
\item[{{\bf Vector} const \&}]{v, }
\item[{size\-\_\-t}]{nearest\-Number, }
\item[{bool}]{compare\-Whole\-Vector}
\end{DoxyParamCaption}
) const\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1KD__Tree_a10e1cac9c14e047d77fb95eaf0b49bd8}


查找 

於set中找尋距離指定向量前 {\ttfamily i} 近的向量, 並依照由近而遠的順序排序. 如果有兩個向量{\ttfamily v1},v2 距離一樣, 且 {\ttfamily cmp}{\ttfamily true} , 則直接依照 {\ttfamily v1$<$v2} 來決定誰在前面. 最後回傳一陣列包含所有解. 

Definition at line 263 of file K\-D\-\_\-\-Tree.\-h.

\hypertarget{classmeow_1_1KD__Tree_a45be7cf06442b1a75902faa266950121}{\index{meow\-::\-K\-D\-\_\-\-Tree@{meow\-::\-K\-D\-\_\-\-Tree}!reset@{reset}}
\index{reset@{reset}!meow::KD_Tree@{meow\-::\-K\-D\-\_\-\-Tree}}
\subsubsection[{reset}]{\setlength{\rightskip}{0pt plus 5cm}template$<$class Vector , class Scalar $>$ void {\bf meow\-::\-K\-D\-\_\-\-Tree}$<$ {\bf Vector}, Scalar $>$\-::reset (
\begin{DoxyParamCaption}
\item[{size\-\_\-t}]{dimension}
\end{DoxyParamCaption}
)\hspace{0.3cm}{\ttfamily [inline]}}}\label{classmeow_1_1KD__Tree_a45be7cf06442b1a75902faa266950121}


清空所有資料並重新給定維度 



Definition at line 295 of file K\-D\-\_\-\-Tree.\-h.



The documentation for this class was generated from the following file\-:\begin{DoxyCompactItemize}
\item 
meowpp/dsa/\hyperlink{KD__Tree_8h}{K\-D\-\_\-\-Tree.\-h}\end{DoxyCompactItemize}