#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.

This website is beyond its original expiry date and the content may be out of date. The site owner has been notified and may choose to extend the expiry date and remove this banner. If you have any questions about this, please visit our support portal.