k-dimensional tree constructable both with 2D (lon,lat) points as with 3D (x,y,z) points More...

#include <KDTree.h>

Inheritance diagram for atlas::util::KDTree< PayloadT, PointT >:

Collaboration diagram for atlas::util::KDTree< PayloadT, PointT >:

Public Types
using	Handle = ObjectHandle< detail::KDTreeBase< PayloadT, PointT > >

using	Implementation = typename Handle::Implementation

using	Point = typename Implementation::Point

using	Payload = typename Implementation::Payload

using	PayloadList = typename Implementation::PayloadList

using	Value = typename Implementation::Value

using	ValueList = typename Implementation::ValueList

using	Handle = ObjectHandle< T >

Public Types inherited from atlas::util::ObjectHandle< detail::KDTreeBase< PayloadT, PointT > >
using	Implementation = detail::KDTreeBase< PayloadT, PointT >

using	Handle = ObjectHandle< detail::KDTreeBase< PayloadT, PointT > >

Public Member Functions
	KDTree (const KDTree &handle)

	KDTree ()
	Construct an empty kd-tree with default geometry (Earth)

	KDTree (const Geometry &geometry)
	Construct an empty kd-tree with custom geometry.

template<typename Tree >
	KDTree (const std::shared_ptr< Tree > &kdtree)
	Construct a shared kd-tree with default geometry (Earth)

template<typename Tree >
	KDTree (const std::shared_ptr< Tree > &kdtree, const Geometry &geometry)
	Construct a shared kd-tree with custom geometry.

void	reserve (idx_t size)
	Reserve memory for building the kd-tree in one shot (optional, at cost of extra memory)

template<typename Point >
void	insert (const Point &p, const Payload &payload)
	Insert spherical point (lon,lat) or 3D cartesian point (x,y,z) More...

void	insert (const Value &value)
	Insert kd-tree value in tree. More...

void	build ()
	Build the kd-tree in one shot, if memory has been reserved. More...

template<typename Longitudes , typename Latitudes , typename Payloads >
void	build (const Longitudes &longitudes, const Latitudes &latitudes, const Payloads &payloads)
	Build with spherical points (lon,lat) where longitudes, latitudes, and payloads are separate containers. More...

template<typename LongitudesIterator , typename LatitudesIterator , typename PayloadsIterator >
void	build (const LongitudesIterator &longitudes_begin, const LongitudesIterator &longitudes_end, const LatitudesIterator &latitudes_begin, const LatitudesIterator &latitudes_end, const PayloadsIterator &payloads_begin, const PayloadsIterator &payloads_end)
	Build with spherical points (lon,lat) given separate iterator ranges for longitudes, latitudes, and payloads. More...

template<typename Points , typename Payloads >
void	build (const Points &points, const Payloads &payloads)
	Build with templated points. More...

template<typename PointIterator , typename PayloadsIterator >
void	build (const PointIterator &points_begin, const PointIterator &points_end, const PayloadsIterator &payloads_begin, const PayloadsIterator &payloads_end)
	Build with spherical points (lon,lat) given separate iterator ranges for longitudes, latitudes, and payloads. More...

void	build (const std::vector< Value > &values)
	Build with vector of Value. More...

bool	empty () const

size_t	size () const

size_t	footprint () const

template<typename Point >
ValueList	closestPoints (const Point &p, size_t k) const
	Find k closest points given a 3D cartesian point (x,y,z) or 2D lonlat point(lon,lat)

template<typename Point >
Value	closestPoint (const Point &p) const
	Find closest point given a 3D cartesian point (x,y,z) or 2D lonlat point(lon,lat)

template<typename Point >
ValueList	closestPointsWithinRadius (const Point &p, double radius) const
	Find all points within a distance of given radius from a given point 3D cartesian point (x,y,z) or a 2D (lon,lat) point.

const Geometry &	geometry () const
	Return geometry used to convert (lon,lat) to (x,y,z) coordinates.

Public Member Functions inherited from atlas::util::ObjectHandle< detail::KDTreeBase< PayloadT, PointT > >
	ObjectHandle (const detail::KDTreeBase< PayloadT, PointT > *object)

	ObjectHandle (const ObjectHandle &handle)

ObjectHandle &	operator= (const ObjectHandle &handle)

ATLAS_ALWAYS_INLINE detail::KDTreeBase< PayloadT, PointT > *	get ()

ATLAS_ALWAYS_INLINE const detail::KDTreeBase< PayloadT, PointT > *	get () const

ATLAS_ALWAYS_INLINE const detail::KDTreeBase< PayloadT, PointT > *	operator-> () const

ATLAS_ALWAYS_INLINE detail::KDTreeBase< PayloadT, PointT > *	operator-> ()

ATLAS_ALWAYS_INLINE const detail::KDTreeBase< PayloadT, PointT > &	operator* () const

ATLAS_ALWAYS_INLINE detail::KDTreeBase< PayloadT, PointT > &	operator* ()

ATLAS_ALWAYS_INLINE void	reset (const detail::KDTreeBase< PayloadT, PointT > *object)

Public Member Functions inherited from atlas::util::ObjectHandleBase
	ObjectHandleBase (const Object *object)

const ObjectHandleBase &	operator= (const ObjectHandleBase &other)

	operator bool () const

void	reset (const Object *other)

int	owners () const

Additional Inherited Members
Protected Attributes inherited from atlas::util::ObjectHandleBase
Object *	object_ {nullptr}

Detailed Description

template<typename PayloadT, typename PointT = Point3>
class atlas::util::KDTree< PayloadT, PointT >

k-dimensional tree constructable both with 2D (lon,lat) points as with 3D (x,y,z) points

The implementation is based on eckit::KDTreeMemory with 3D (x,y,z) points. 2D points (lon,lat) are converted when needed to 3D during insertion, and during search, so that a search always happens with 3D cartesian points.

Example:

Construct a KDTree, given a list_of_lonlat_points (e.g. std::vector<PointLonLat> or other container) A payload given is the index in this list.

KDTree<idx_t> search;
search.reserve( list_of_lonlat_points.size() );
idx_t n{0};
for ( auto& point : list_of_lonlat_points ) {
    search.insert( point, n++ );
}
search.build();

We can now do e.g. a search for the nearest 4 neighbours (k=4) sorted by shortest distance

idx_t k = 4;

auto neighbours = search.closestPoints( PointLonLat{180., 45.}, k ).payloads();

The variable neighbours is now a container of indices (the payloads) of the 4 nearest points

Member Function Documentation

◆ build() [1/6]

template<typename PayloadT , typename PointT = Point3>

void atlas::util::KDTree< PayloadT, PointT >::build ( )

inline

Build the kd-tree in one shot, if memory has been reserved.

This will need to be called before all search functions like closestPoints().

Postcondition: The KDTree is ready to be used

◆ build() [2/6]

template<typename PayloadT , typename PointT = Point3>

template<typename Longitudes , typename Latitudes , typename Payloads >

void atlas::util::KDTree< PayloadT, PointT >::build	(	const Longitudes &	longitudes,
		const Latitudes &	latitudes,
		const Payloads &	payloads
	)

inline

Build with spherical points (lon,lat) where longitudes, latitudes, and payloads are separate containers.

Memory will be reserved with reserve() to match the size

Postcondition: The KDTree is ready to be used

◆ build() [3/6]

template<typename PayloadT , typename PointT = Point3>

template<typename LongitudesIterator , typename LatitudesIterator , typename PayloadsIterator >

void atlas::util::KDTree< PayloadT, PointT >::build	(	const LongitudesIterator &	longitudes_begin,
		const LongitudesIterator &	longitudes_end,
		const LatitudesIterator &	latitudes_begin,
		const LatitudesIterator &	latitudes_end,
		const PayloadsIterator &	payloads_begin,
		const PayloadsIterator &	payloads_end
	)

inline

Build with spherical points (lon,lat) given separate iterator ranges for longitudes, latitudes, and payloads.

Memory will be reserved with reserve() to match the size

Postcondition: The KDTree is ready to be used

◆ build() [4/6]

template<typename PayloadT , typename PointT = Point3>

template<typename Points , typename Payloads >

void atlas::util::KDTree< PayloadT, PointT >::build	(	const Points &	points,
		const Payloads &	payloads
	)

inline

Build with templated points.

Points can be either 2D (lon,lat) or 3D (x,y,z) Memory will be reserved with reserve() to match the size

Postcondition: The KDTree is ready to be used

◆ build() [5/6]

template<typename PayloadT , typename PointT = Point3>

template<typename PointIterator , typename PayloadsIterator >

void atlas::util::KDTree< PayloadT, PointT >::build	(	const PointIterator &	points_begin,
		const PointIterator &	points_end,
		const PayloadsIterator &	payloads_begin,
		const PayloadsIterator &	payloads_end
	)

inline

Build with spherical points (lon,lat) given separate iterator ranges for longitudes, latitudes, and payloads.

Memory will be reserved with reserve() to match the size

Postcondition: The KDTree is ready to be used

◆ build() [6/6]

template<typename PayloadT , typename PointT = Point3>

void atlas::util::KDTree< PayloadT, PointT >::build ( const std::vector< Value > & values )

inline

Build with vector of Value.

Postcondition: The KDTree is ready to be used

◆ insert() [1/2]

template<typename PayloadT , typename PointT = Point3>

template<typename Point >

void atlas::util::KDTree< PayloadT, PointT >::insert	(	const Point &	p,
		const Payload &	payload
	)

inline

Insert spherical point (lon,lat) or 3D cartesian point (x,y,z)

Warning: If memory has been reserved with reserve(), insertion will be delayed until build() is called.

◆ insert() [2/2]

template<typename PayloadT , typename PointT = Point3>

void atlas::util::KDTree< PayloadT, PointT >::insert ( const Value & value )

inline

Insert kd-tree value in tree.

Warning: If memory has been reserved with reserve(), insertion will be delayed until build() is called.

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

src/atlas/util/KDTree.h

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

template<typename PayloadT, typename PointT = Point3> class atlas::util::KDTree< PayloadT, PointT >

Example:

Member Function Documentation

◆ build() [1/6]

◆ build() [2/6]

◆ build() [3/6]

◆ build() [4/6]

◆ build() [5/6]

◆ build() [6/6]

◆ insert() [1/2]

◆ insert() [2/2]

template<typename PayloadT, typename PointT = Point3>
class atlas::util::KDTree< PayloadT, PointT >