Kd樹按空間劃分生成葉子節(jié)點(diǎn)，各個(gè)葉子節(jié)點(diǎn)里存放點(diǎn)數(shù)據(jù)，其可以按半徑搜索或鄰區(qū)搜索。PCL中的Kd tree的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)使用了FLANN以便可以快速的進(jìn)行鄰區(qū)搜索。FLANN?is a library for performing fast approximate nearest neighbor searches in high dimensional spaces。下面是一個(gè)最基本的例子，只尋找一個(gè)最近點(diǎn)：

#include <pcl/point_cloud.h> #include <pcl/kdtree/kdtree_flann.h>#include <iostream> #include <vector> #include <ctime>int main (int argc, char** argv) {srand (time (NULL)); //seeds rand() with the system time time_t begin,end;begin = clock(); //開始計(jì)時(shí)//-------------------------------------------------------------------------------pcl::PointCloud<pcl::PointXYZ>::Ptr cloud (new pcl::PointCloud<pcl::PointXYZ>);// Generate pointcloud datacloud->width = 400000;cloud->height = 1;cloud->points.resize (cloud->width * cloud->height);// fills a PointCloud with random datafor (size_t i = 0; i < cloud->points.size (); ++i){cloud->points[i].x = 1024.0f * rand () / (RAND_MAX + 1.0f);cloud->points[i].y = 1024.0f * rand () / (RAND_MAX + 1.0f);cloud->points[i].z = 1024.0f * rand () / (RAND_MAX + 1.0f);}// creates kdtree objectpcl::KdTreeFLANN<pcl::PointXYZ> kdtree;// sets our randomly created cloud as the input kdtree.setInputCloud (cloud);//create a “searchPoint” which is assigned random coordinates pcl::PointXYZ searchPoint;searchPoint.x = 1024.0f * rand () / (RAND_MAX + 1.0f);searchPoint.y = 1024.0f * rand () / (RAND_MAX + 1.0f);searchPoint.z = 1024.0f * rand () / (RAND_MAX + 1.0f);// K nearest neighbor searchint K = 1;std::vector<int> pointIdxNKNSearch(K);std::vector<float> pointNKNSquaredDistance(K);std::cout << "K nearest neighbor search at (" << searchPoint.x << " " << searchPoint.y << " " << searchPoint.z<< ") with K=" << K << std::endl;/***********************************************************************************************template<typename PointT> virtual int pcl::KdTree< PointT >::nearestKSearch ( const PointT & p_q, int k, std::vector< int > & k_indices, std::vector< float > & k_sqr_distances ) const [pure virtual] Search for k-nearest neighbors for the given query point. Parameters:[in] the given query point [in] k the number of neighbors to search for [out] the resultant indices of the neighboring points[out] the resultant squared distances to the neighboring pointsReturns:number of neighbors found ********************************************************************************************/if ( kdtree.nearestKSearch (searchPoint, K, pointIdxNKNSearch, pointNKNSquaredDistance) > 0 ){for (size_t i = 0; i < pointIdxNKNSearch.size (); ++i)std::cout << " " << cloud->points[ pointIdxNKNSearch[i] ].x << " " << cloud->points[ pointIdxNKNSearch[i] ].y << " " << cloud->points[ pointIdxNKNSearch[i] ].z << " (squared distance: " << pointNKNSquaredDistance[i] << ")" << std::endl;}//--------------------------------------------------------------------------------------------end = clock(); //結(jié)束計(jì)時(shí)double Times = double(end - begin) / CLOCKS_PER_SEC; //將clock()函數(shù)的結(jié)果轉(zhuǎn)化為以秒為單位的量 std::cout<<"time: "<<Times<<"s"<<std::endl;return 0; }

　　生成四十萬個(gè)隨機(jī)點(diǎn)，release版本下測試0.3s左右找到最近點(diǎn)，這比之前自己寫的Kd樹不知快到哪里去了。當(dāng)然自己寫只是為了更好的理解其中的原理，真要用的時(shí)候還得靠別人的輪子...

?

參考：

How to use a KdTree to search

Module kdtree

轉(zhuǎn)載于:https://www.cnblogs.com/21207-iHome/p/6103354.html

總結(jié)

以上是生活随笔為你收集整理的PCL点云库：Kd树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。