#include <atlas/util/KDTree.h>

template<typename PayloadT, typename PointT = Point3>

atlas::util::KDTree class

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

Base classes

class ObjectHandle<detail::KDTreeBase<PayloadT, Point3>>

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

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