Base class for nearest neighbor search using KdTree. More...

#include <easy3d/kdtree/kdtree_search.h>

Inheritance diagram for KdTreeSearch:

Public Member Functions
	KdTreeSearch (const PointCloud *cloud)
	Constructor.

	KdTreeSearch (const std::vector< vec3 > &points)
	Constructor.

Closest point query
virtual int	find_closest_point (const vec3 &p, float &squared_distance) const =0
	Queries the closest point for a given point.

virtual int	find_closest_point (const vec3 &p) const =0
	Queries the closest point for a given point.

K nearest neighbors search
virtual void	find_closest_k_points (const vec3 &p, int k, std::vector< int > &neighbors, std::vector< float > &squared_distances) const =0
	Queries the K nearest neighbors for a given point.

virtual void	find_closest_k_points (const vec3 &p, int k, std::vector< int > &neighbors) const =0
	Queries the K nearest neighbors for a given point.

Fixed radius search
virtual void	find_points_in_range (const vec3 &p, float squared_radius, std::vector< int > &neighbors, std::vector< float > &squared_distances) const =0
	Queries the nearest neighbors within a fixed range.

virtual void	find_points_in_range (const vec3 &p, float squared_radius, std::vector< int > &neighbors) const =0
	Queries the nearest neighbors within a fixed range.

Detailed Description

Base class for nearest neighbor search using KdTree.

See also: KdTreeSearch_ANN, KdTreeSearch_ETH, KdTreeSearch_FLANN, and KdTreeSearch_NanoFLANN

Easy3D has a collection of KdTree implementations, including ANN, ETH, FLANN, and NanoFLANN and tried to get the best performance of each implementation. Runtime tests (on Windows, using a Visual C++ 2008, release build) indicated that the ETH implementation has the best performance. Bellow is the statistic summary of the test on two point clouds.

Build: time for constructing the kd-tree.
Single: time for querying closest vertex (for each point in the point cloud).
KNN: time for querying K(=16) closest vertex.
Radius: time for querying closest vertex within a radius.

Test 1: 362, 271 points (the Stanford bunny). radius = 0.001

--------------------------------------------------------------------------------------
      Build         |       Single        |        KNN         |       Radius
--------------------|---------------------|--------------------|---------------------
ANN    ETH   FLANN  |  ANN   ETH   FLANN  |  ANN   ETH   FLANN |  ANN   ETH   FLANN
--------------------|---------------------|--------------------|---------------------
0.14   0.05   0.12  |  0.17  0.11   0.71  |  1.33  1.0   1.48  |  1.32  1.01  1.51
--------------------------------------------------------------------------------------

Test 2: 4, 116, 466 points (an noisy urban scan). radius = 0.03

--------------------------------------------------------------------------------------
      Build         |       Single        |        KNN          |       Radius
--------------------|---------------------|---------------------|---------------------
ANN    ETH   FLANN  |  ANN   ETH   FLANN  |  ANN   ETH   FLANN  |  ANN    ETH   FLANN
--------------------|---------------------|---------------------|---------------------
2.2   0.76   1.88   |  2.61  1.84  11.8   |  20.8  13.5  22.0   |  8.75  4.79   15.1
--------------------------------------------------------------------------------------

Attention: KdTreeSearch_FLANN and KdTreeSearch_NanoFLANN are thread-safe. Others seem not (not tested yet).

Constructor & Destructor Documentation

◆ KdTreeSearch() [1/2]

KdTreeSearch ( const PointCloud * cloud )

explicit

Constructor.

Parameters

cloud The point cloud for which a KdTree will be constructed.

◆ KdTreeSearch() [2/2]

KdTreeSearch ( const std::vector< vec3 > & points )

explicit

Constructor.

Parameters

points The points for which a KdTree will be constructed.

Member Function Documentation

◆ find_closest_k_points() [1/2]

virtual void find_closest_k_points	(	const vec3 &	p,
		int	k,
		std::vector< int > &	neighbors ) const

pure virtual

Queries the K nearest neighbors for a given point.

Parameters

p	The query point.
k	The number of required neighbors.
neighbors	The indices of the neighbors found (the same as in the original point cloud).

Implemented in KdTreeSearch_ANN, KdTreeSearch_ETH, KdTreeSearch_FLANN, and KdTreeSearch_NanoFLANN.

◆ find_closest_k_points() [2/2]

virtual void find_closest_k_points	(	const vec3 &	p,
		int	k,
		std::vector< int > &	neighbors,
		std::vector< float > &	squared_distances ) const

pure virtual

Queries the K nearest neighbors for a given point.

Parameters

p	The query point.
k	The number of required neighbors.
neighbors	The indices of the neighbors found (the same as in the original point cloud).
squared_distances	The squared distances between the query point and its K nearest neighbors. The values are stored in accordance with their indices.

Note: The squared distances are returned by the argument squared_distances.

Implemented in KdTreeSearch_ANN, KdTreeSearch_ETH, KdTreeSearch_FLANN, and KdTreeSearch_NanoFLANN.

◆ find_closest_point() [1/2]

virtual int find_closest_point ( const vec3 & p ) const

pure virtual

Queries the closest point for a given point.

Parameters

p	The query point.

Returns: The index of the nearest neighbor found (the same as in the original point cloud).

Implemented in KdTreeSearch_ANN, KdTreeSearch_ETH, KdTreeSearch_FLANN, and KdTreeSearch_NanoFLANN.

◆ find_closest_point() [2/2]

virtual int find_closest_point	(	const vec3 &	p,
		float &	squared_distance ) const

pure virtual

Queries the closest point for a given point.

Parameters

p	The query point.
squared_distance	The squared distance between the query point and its closest neighbor.

Note: A squared distance is returned by the second argument squared_distance.

Returns: The index of the nearest neighbor found (the same as in the original point cloud).

Implemented in KdTreeSearch_ANN, KdTreeSearch_ETH, KdTreeSearch_FLANN, and KdTreeSearch_NanoFLANN.

◆ find_points_in_range() [1/2]

virtual void find_points_in_range	(	const vec3 &	p,
		float	squared_radius,
		std::vector< int > &	neighbors ) const

pure virtual

Queries the nearest neighbors within a fixed range.

Parameters

p	The query point.
squared_radius	The search range (which is required to be squared).
neighbors	The indices of the neighbors found (the same as in the original point cloud).

Implemented in KdTreeSearch_ANN, KdTreeSearch_ETH, KdTreeSearch_FLANN, and KdTreeSearch_NanoFLANN.

◆ find_points_in_range() [2/2]

virtual void find_points_in_range	(	const vec3 &	p,
		float	squared_radius,
		std::vector< int > &	neighbors,
		std::vector< float > &	squared_distances ) const

pure virtual

Queries the nearest neighbors within a fixed range.

Parameters

p	The query point.
squared_radius	The search range (which is required to be squared).
neighbors	The indices of the neighbors found (the same as in the original point cloud).
squared_distances	The squared distances between the query point and the neighbors found. The values are stored in accordance with their indices.

Note: The squared distances are returned by the argument squared_distances.

Implemented in KdTreeSearch_ANN, KdTreeSearch_ETH, KdTreeSearch_FLANN, and KdTreeSearch_NanoFLANN.

The documentation for this class was generated from the following files:

G:/3_code/Easy3D/easy3d/kdtree/kdtree_search.h
G:/3_code/Easy3D/easy3d/kdtree/kdtree_search.cpp

Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ KdTreeSearch() [1/2]

◆ KdTreeSearch() [2/2]

Member Function Documentation

◆ find_closest_k_points() [1/2]

◆ find_closest_k_points() [2/2]

◆ find_closest_point() [1/2]

◆ find_closest_point() [2/2]

◆ find_points_in_range() [1/2]

◆ find_points_in_range() [2/2]