from:https://blog.csdn.net/qq_25491201/article/details/51135054

下面這個教程我們將學會怎么用KdTree找一個特殊點附近的K個最近鄰，然后我們也將復習怎么通過一個特殊的半徑來找里面所有的近鄰。

一個k-d樹，或者k維的樹是一個計算機科學里面的數據結構。它是一個有其它約束影響的二叉搜索樹。K-d樹是在深度和最近鄰搜索里面很有用的。我們這次的目的是生成一個3維的k-d trees。一個k-d tree的每個層次在某個維度上分割成所有的子樹，使用一個垂直于相應坐標軸的高維平面。在樹的根部，所有的子樹將會被分割以第一維(如果第一維坐標系比根部少，它將會成為左子樹，如果比根部多，它將會成為右子樹)。每一層的樹將會在下一層進行分叉，它會跳轉到第一層如果全部都分完了。最有效的去建立k-d tree的方法是使用一個分割的方法，就像快速排序。你可以在你的左子樹和右子樹上重復這一過程，直到最后一個你要去分割的樹只有一個元素。

2維的k-d樹

下面是一個最近鄰搜索的工作

?

代碼

#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));

? pcl::PointCloud<pcl::PointXYZ>::Ptr cloud (new pcl::PointCloud<pcl::PointXYZ>);

? // Generate pointcloud data
? cloud->width = 1000;
? cloud->height = 1;
? cloud->points.resize (cloud->width * cloud->height);

? for (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);
? }

? pcl::KdTreeFLANN<pcl::PointXYZ> kdtree;

? kdtree.setInputCloud (cloud);

? 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 search

? int K = 10;

? 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;

? 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;
? }

? // Neighbors within radius search

? std::vector<int> pointIdxRadiusSearch;
? std::vector<float> pointRadiusSquaredDistance;

? float radius = 256.0f * rand () / (RAND_MAX + 1.0f);

? std::cout << "Neighbors within radius search at (" << searchPoint.x?
? ? ? ? ? ? << " " << searchPoint.y?
? ? ? ? ? ? << " " << searchPoint.z
? ? ? ? ? ? << ") with radius=" << radius << std::endl;

? if ( kdtree.radiusSearch (searchPoint, radius, pointIdxRadiusSearch, pointRadiusSquaredDistance) > 0 )
? {
? ? for (size_t i = 0; i < pointIdxRadiusSearch.size (); ++i)
? ? ? std::cout << " ? ?" ?<< ? cloud->points[ pointIdxRadiusSearch[i] ].x?
? ? ? ? ? ? ? ? << " " << cloud->points[ pointIdxRadiusSearch[i] ].y?
? ? ? ? ? ? ? ? << " " << cloud->points[ pointIdxRadiusSearch[i] ].z?
? ? ? ? ? ? ? ? << " (squared distance: " << pointRadiusSquaredDistance[i] << ")" << std::endl;
? }

? return 0;
}
下面的代碼是創造了kdtree這個對象，并把我們隨機生成的點云作為輸入。

? pcl::KdTreeFLANN<pcl::PointXYZ> kdtree;

? kdtree.setInputCloud (cloud);

? 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);
我們接下去創造了一個整數(通常設置為10)和兩個向量存儲搜索后的K個最近鄰。

? // K nearest neighbor search

? int K = 10;

? 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;
假設我們的kdtree返回了大于0個近鄰。那么它將打印出在我們"searchPoint"附近的10個最近的鄰居并把它們存到先前創立的向量中。

? 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;
? }
?// Neighbors within radius search

? std::vector<int> pointIdxRadiusSearch;
? std::vector<float> pointRadiusSquaredDistance;

? float radius = 256.0f * rand () / (RAND_MAX + 1.0f);
我們把向量里面的點打印出來

? if ( kdtree.radiusSearch (searchPoint, radius, pointIdxRadiusSearch, pointRadiusSquaredDistance) > 0 )
? {
? ? for (size_t i = 0; i < pointIdxRadiusSearch.size (); ++i)
? ? ? std::cout << " ? ?" ?<< ? cloud->points[ pointIdxRadiusSearch[i] ].x?
? ? ? ? ? ? ? ? << " " << cloud->points[ pointIdxRadiusSearch[i] ].y?
? ? ? ? ? ? ? ? << " " << cloud->points[ pointIdxRadiusSearch[i] ].z?
? ? ? ? ? ? ? ? << " (squared distance: " << pointRadiusSquaredDistance[i] << ")" << std::endl;
? }
結果

K nearest neighbor search at (455.807 417.256 406.502) with K=10
? 494.728 371.875 351.687 (squared distance: 6578.99)
? 506.066 420.079 478.278 (squared distance: 7685.67)
? 368.546 427.623 416.388 (squared distance: 7819.75)
? 474.832 383.041 323.293 (squared distance: 8456.34)
? 470.992 334.084 468.459 (squared distance: 10986.9)
? 560.884 417.637 364.518 (squared distance: 12803.8)
? 466.703 475.716 306.269 (squared distance: 13582.9)
? 456.907 336.035 304.529 (squared distance: 16996.7)
? 452.288 387.943 279.481 (squared distance: 17005.9)
? 476.642 410.422 268.057 (squared distance: 19647.9)
Neighbors within radius search at (455.807 417.256 406.502) with radius=225.932
? 494.728 371.875 351.687 (squared distance: 6578.99)
? 506.066 420.079 478.278 (squared distance: 7685.67)
? 368.546 427.623 416.388 (squared distance: 7819.75)
? 474.832 383.041 323.293 (squared distance: 8456.34)
? 470.992 334.084 468.459 (squared distance: 10986.9)
? 560.884 417.637 364.518 (squared distance: 12803.8)
? 466.703 475.716 306.269 (squared distance: 13582.9)
? 456.907 336.035 304.529 (squared distance: 16996.7)
? 452.288 387.943 279.481 (squared distance: 17005.9)
? 476.642 410.422 268.057 (squared distance: 19647.9)
? 499.429 541.532 351.35 (squared distance: 20389)
? 574.418 452.961 334.7 (squared distance: 20498.9)
? 336.785 391.057 488.71 (squared distance: 21611)
? 319.765 406.187 350.955 (squared distance: 21715.6)
? 528.89 289.583 378.979 (squared distance: 22399.1)
? 504.509 459.609 541.732 (squared distance: 22452.8)
? 539.854 349.333 300.395 (squared distance: 22936.3)
? 548.51 458.035 292.812 (squared distance: 23182.1)
? 546.284 426.67 535.989 (squared distance: 25041.6)
? 577.058 390.276 508.597 (squared distance: 25853.1)
? 543.16 458.727 276.859 (squared distance: 26157.5)
? 613.997 387.397 443.207 (squared distance: 27262.7)
? 608.235 467.363 327.264 (squared distance: 32023.6)
? 506.842 591.736 391.923 (squared distance: 33260.3)
? 529.842 475.715 241.532 (squared distance: 36113.7)
? 485.822 322.623 244.347 (squared distance: 36150.5)
? 362.036 318.014 269.201 (squared distance: 37493.6)
? 493.806 600.083 462.742 (squared distance: 38032.3)
? 392.315 368.085 585.37 (squared distance: 38442.9)
? 303.826 428.659 533.642 (squared distance: 39392.8)
? 616.492 424.551 289.524 (squared distance: 39556.8)
? 320.563 333.216 278.242 (squared distance: 41804.5)
? 646.599 502.256 424.46 (squared distance: 43948.8)
? 556.202 325.013 568.252 (squared distance: 44751)
? 291.27 497.352 515.938 (squared distance: 45463.9)
? 286.483 322.401 495.377 (squared distance: 45567.2)
? 367.288 550.421 550.551 (squared distance: 46318.6)
? 595.122 582.77 394.894 (squared distance: 46938.1)
? 256.784 499.401 379.931 (squared distance: 47064.1)
? 430.782 230.854 293.829 (squared distance: 48067.2)
? 261.051 486.593 329.854 (squared distance: 48612.7)
? 602.061 327.892 545.269 (squared distance: 48632.4)
? 347.074 610.994 395.622 (squared distance: 49475.6)
? 482.876 284.894 583.888 (squared distance: 49718.6)
? 356.962 247.285 514.959 (squared distance: 50423.7)
? 282.065 509.488 516.216 (squared distance: 50730.4)
---------------------?
作者：Spongelady?
來源：CSDN?
原文：https://blog.csdn.net/qq_25491201/article/details/51135054?
版權聲明：本文為博主原創文章，轉載請附上博文鏈接！