#include <atlas/util/KDTree.h>
template<typename PayloadT, typename PointT = Point3>
atlas::util::KDTree class

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

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

Constructors, destructors, conversion operators

KDTree()
Construct an empty kd-tree with default geometry (Earth)
KDTree(const Geometry& geometry)
Construct an empty kd-tree with custom geometry.
KDTree(const eckit::Configuration& config)
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.

Public functions

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)
void insert(const Value& value)
Insert kd-tree value in tree.
void build()
Build the kd-tree in one shot, if memory has been reserved. This will need to be called before all search functions like closestPoints().
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. Memory will be reserved with reserve() to match the size.
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. Memory will be reserved with reserve() to match the size.
template<typename Points, typename Payloads>
void build(const Points& points, const Payloads& payloads)
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.
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. Memory will be reserved with reserve() to match the size.
void build(const std::vector<Value>& values)
Build with vector of Value.
auto empty() const -> bool
auto size() const -> size_t
auto footprint() const -> size_t
template<typename Point>
auto closestPoints(const Point& p, size_t k) const -> ValueList
Find k closest points given a 3D cartesian point (x,y,z) or 2D lonlat point(lon,lat)
template<typename Point>
auto closestPoint(const Point& p) const -> Value
Find closest point given a 3D cartesian point (x,y,z) or 2D lonlat point(lon,lat)
template<typename Point>
auto closestPointsWithinRadius(const Point& p, double radius) const -> ValueList
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.
auto geometry() const -> const Geometry&
Return geometry used to convert (lon,lat) to (x,y,z) coordinates.

Function documentation

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

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

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

Insert kd-tree value in tree.

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

Build the kd-tree in one shot, if memory has been reserved. This will need to be called before all search functions like closestPoints().

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

Build with spherical points (lon,lat) where longitudes, latitudes, and payloads are separate containers. Memory will be reserved with reserve() to match the size.

template<typename PayloadT, typename PointT> 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)

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.

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

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.

template<typename PayloadT, typename PointT> 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)

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.

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

Build with vector of Value.