| 1 |
/* |
| 2 |
* (C) Copyright 2013 ECMWF. |
| 3 |
* |
| 4 |
* This software is licensed under the terms of the Apache Licence Version 2.0 |
| 5 |
* which can be obtained at http://www.apache.org/licenses/LICENSE-2.0. |
| 6 |
* In applying this licence, ECMWF does not waive the privileges and immunities |
| 7 |
* granted to it by virtue of its status as an intergovernmental organisation |
| 8 |
* nor does it submit to any jurisdiction. |
| 9 |
*/ |
| 10 |
|
| 11 |
#pragma once |
| 12 |
|
| 13 |
#include "eckit/config/Configuration.h" |
| 14 |
|
| 15 |
#include "atlas/util/Geometry.h" |
| 16 |
#include "atlas/util/ObjectHandle.h" |
| 17 |
#include "atlas/util/detail/KDTree.h" |
| 18 |
|
| 19 |
namespace atlas { |
| 20 |
namespace util { |
| 21 |
|
| 22 |
//------------------------------------------------------------------------------------------------------ |
| 23 |
|
| 24 |
/// @brief k-dimensional tree constructable both with 2D (lon,lat) points as with 3D (x,y,z) points |
| 25 |
/// |
| 26 |
/// The implementation is based on eckit::KDTreeMemory with 3D (x,y,z) points. |
| 27 |
/// 2D points (lon,lat) are converted when needed to 3D during insertion, and during search, so that |
| 28 |
/// a search always happens with 3D cartesian points. |
| 29 |
/// |
| 30 |
/// ### Example: |
| 31 |
/// |
| 32 |
/// Construct a KDTree, given a `list_of_lonlat_points` (e.g. `std::vector<PointLonLat>` or other container) |
| 33 |
/// A payload given is the index in this list. |
| 34 |
/// @code{.cpp} |
| 35 |
/// KDTree<idx_t> search; |
| 36 |
/// search.reserve( list_of_lonlat_points.size() ); |
| 37 |
/// idx_t n{0}; |
| 38 |
/// for ( auto& point : list_of_lonlat_points ) { |
| 39 |
/// search.insert( point, n++ ); |
| 40 |
/// } |
| 41 |
/// search.build(); |
| 42 |
/// @endcode |
| 43 |
/// We can now do e.g. a search for the nearest 4 neighbours (k=4) sorted by shortest distance |
| 44 |
/// @code{.cpp} |
| 45 |
/// idx_t k = 4; |
| 46 |
/// auto neighbours = search.closestPoints( PointLonLat{180., 45.}, k ).payloads(); |
| 47 |
/// @endcode |
| 48 |
/// The variable `neighbours` is now a container of indices (the payloads) of the 4 nearest points |
| 49 |
|
| 50 |
template <typename PayloadT, typename PointT = Point3> |
| 51 |
class KDTree : public ObjectHandle<detail::KDTreeBase<PayloadT, PointT>> { |
| 52 |
public: |
| 53 |
using Handle = ObjectHandle<detail::KDTreeBase<PayloadT, PointT>>; |
| 54 |
using Implementation = typename Handle::Implementation; |
| 55 |
using Point = typename Implementation::Point; |
| 56 |
using Payload = typename Implementation::Payload; |
| 57 |
using PayloadList = typename Implementation::PayloadList; |
| 58 |
using Value = typename Implementation::Value; |
| 59 |
using ValueList = typename Implementation::ValueList; |
| 60 |
|
| 61 |
using Handle::get; |
| 62 |
using Handle::Handle; |
| 63 |
|
| 64 |
public: |
| 65 |
//-------------------------------------------------------------------------------------- |
| 66 |
// Constructors |
| 67 |
|
| 68 |
/// @brief Construct an empty kd-tree with default geometry (Earth) |
| 69 |
KDTree(): Handle(new detail::KDTreeMemory<Payload, Point>()) {} |
| 70 |
|
| 71 |
/// @brief Construct an empty kd-tree with custom geometry |
| 72 |
KDTree(const Geometry& geometry): Handle(new detail::KDTreeMemory<Payload, Point>(geometry)) {} |
| 73 |
|
| 74 |
/// @brief Construct an empty kd-tree with custom geometry |
| 75 |
KDTree(const eckit::Configuration& config): |
| 76 |
KDTree(Geometry(config.getString("geometry","Earth"))) {} |
| 77 |
|
| 78 |
/// @brief Construct a shared kd-tree with default geometry (Earth) |
| 79 |
template <typename Tree> |
| 80 |
KDTree(const std::shared_ptr<Tree>& kdtree): Handle(new detail::KDTree_eckit<Tree, Payload, Point>(kdtree)) {} |
| 81 |
|
| 82 |
/// @brief Construct a shared kd-tree with custom geometry |
| 83 |
template <typename Tree> |
| 84 |
KDTree(const std::shared_ptr<Tree>& kdtree, const Geometry& geometry): |
| 85 |
Handle(new detail::KDTree_eckit<Tree, Payload, Point>(kdtree, geometry)) {} |
| 86 |
|
| 87 |
//-------------------------------------------------------------------------------------- |
| 88 |
// Methods to build the KDTree |
| 89 |
|
| 90 |
/// @brief Reserve memory for building the kd-tree in one shot (optional, at cost of extra memory) |
| 91 |
void reserve(idx_t size) { get()->reserve(size); } |
| 92 |
|
| 93 |
/// @brief Insert spherical point (lon,lat) or 3D cartesian point (x,y,z) |
| 94 |
/// @warning If memory has been reserved with reserve(), insertion will be delayed until build() is called. |
| 95 |
template <typename Point> |
| 96 |
void insert(const Point& p, const Payload& payload) { |
| 97 |
get()->insert(p, payload); |
| 98 |
} |
| 99 |
|
| 100 |
/// @brief Insert kd-tree value in tree |
| 101 |
/// @warning If memory has been reserved with reserve(), insertion will be delayed until build() is called. |
| 102 |
void insert(const Value& value) { get()->insert(value); } |
| 103 |
|
| 104 |
/// @brief Build the kd-tree in one shot, if memory has been reserved. |
| 105 |
/// This will need to be called before all search functions like closestPoints(). |
| 106 |
/// @post The KDTree is ready to be used |
| 107 |
void build() { get()->build(); } |
| 108 |
|
| 109 |
/// @brief Build with spherical points (lon,lat) where longitudes, latitudes, and payloads are separate containers. |
| 110 |
/// Memory will be reserved with reserve() to match the size |
| 111 |
/// @post The KDTree is ready to be used |
| 112 |
template <typename Longitudes, typename Latitudes, typename Payloads> |
| 113 |
void build(const Longitudes& longitudes, const Latitudes& latitudes, const Payloads& payloads) { |
| 114 |
get()->build(longitudes, latitudes, payloads); |
| 115 |
} |
| 116 |
|
| 117 |
/// @brief Build with spherical points (lon,lat) given separate iterator ranges for longitudes, latitudes, and payloads. |
| 118 |
/// Memory will be reserved with reserve() to match the size |
| 119 |
/// @post The KDTree is ready to be used |
| 120 |
template <typename LongitudesIterator, typename LatitudesIterator, typename PayloadsIterator> |
| 121 |
void build(const LongitudesIterator& longitudes_begin, const LongitudesIterator& longitudes_end, |
| 122 |
const LatitudesIterator& latitudes_begin, const LatitudesIterator& latitudes_end, |
| 123 |
const PayloadsIterator& payloads_begin, const PayloadsIterator& payloads_end) { |
| 124 |
get()->build(longitudes_begin, longitudes_end, latitudes_begin, latitudes_end, payloads_begin, payloads_end); |
| 125 |
} |
| 126 |
|
| 127 |
/// @brief Build with templated points. Points can be either 2D (lon,lat) or 3D (x,y,z) |
| 128 |
/// Memory will be reserved with reserve() to match the size |
| 129 |
/// @post The KDTree is ready to be used |
| 130 |
template <typename Points, typename Payloads> |
| 131 |
void build(const Points& points, const Payloads& payloads) { |
| 132 |
get()->build(points, payloads); |
| 133 |
} |
| 134 |
|
| 135 |
/// @brief Build with spherical points (lon,lat) given separate iterator ranges for longitudes, latitudes, and payloads. |
| 136 |
/// Memory will be reserved with reserve() to match the size |
| 137 |
/// @post The KDTree is ready to be used |
| 138 |
template <typename PointIterator, typename PayloadsIterator> |
| 139 |
void build(const PointIterator& points_begin, const PointIterator& points_end, |
| 140 |
const PayloadsIterator& payloads_begin, const PayloadsIterator& payloads_end) { |
| 141 |
get()->build(points_begin, points_end, payloads_begin, payloads_end); |
| 142 |
} |
| 143 |
|
| 144 |
/// @brief Build with vector of Value |
| 145 |
/// @post The KDTree is ready to be used |
| 146 |
void build(const std::vector<Value>& values) { get()->build(values); } |
| 147 |
|
| 148 |
//-------------------------------------------------------------------------------------- |
| 149 |
// Methods to access the KDTree |
| 150 |
|
| 151 |
bool empty() const { return get()->empty(); } |
| 152 |
|
| 153 |
size_t size() const { return get()->size(); } |
| 154 |
|
| 155 |
size_t footprint() const { return get()->footprint(); } |
| 156 |
|
| 157 |
/// @brief Find k closest points given a 3D cartesian point (x,y,z) or 2D lonlat point(lon,lat) |
| 158 |
template <typename Point> |
| 159 |
ValueList closestPoints(const Point& p, size_t k) const { |
| 160 |
return get()->closestPoints(p, k); |
| 161 |
} |
| 162 |
|
| 163 |
/// @brief Find closest point given a 3D cartesian point (x,y,z) or 2D lonlat point(lon,lat) |
| 164 |
template <typename Point> |
| 165 |
Value closestPoint(const Point& p) const { |
| 166 |
return get()->closestPoint(p); |
| 167 |
} |
| 168 |
|
| 169 |
/// @brief Find all points within a distance of given radius from a given point 3D cartesian point (x,y,z) |
| 170 |
/// or a 2D (lon,lat) point |
| 171 |
template <typename Point> |
| 172 |
ValueList closestPointsWithinRadius(const Point& p, double radius) const { |
| 173 |
return get()->closestPointsWithinRadius(p, radius); |
| 174 |
} |
| 175 |
|
| 176 |
/// @brief Return geometry used to convert (lon,lat) to (x,y,z) coordinates |
| 177 |
const Geometry& geometry() const { return get()->geometry(); } |
| 178 |
}; |
| 179 |
|
| 180 |
//------------------------------------------------------------------------------------------------------ |
| 181 |
|
| 182 |
using IndexKDTree2D = KDTree<idx_t, Point2>; // 2D search: implementation is using 2D points only |
| 183 |
using IndexKDTree3D = KDTree<idx_t, Point3>; // 3D search: lonlat (2D) to xyz (3D) conversion is done internally |
| 184 |
using IndexKDTree = IndexKDTree3D; |
| 185 |
|
| 186 |
// ------------------------------------------------------------------ |
| 187 |
// C wrapper interfaces to C++ routines |
| 188 |
|
| 189 |
extern "C" { |
| 190 |
IndexKDTree::Implementation* atlas__IndexKDTree__new(); |
| 191 |
IndexKDTree::Implementation* atlas__IndexKDTree__new_geometry(const Geometry::Implementation* geometry); |
| 192 |
void atlas__IndexKDTree__delete(IndexKDTree::Implementation* This); |
| 193 |
void atlas__IndexKDTree__reserve(IndexKDTree::Implementation* This, const idx_t size); |
| 194 |
void atlas__IndexKDTree__insert(IndexKDTree::Implementation* This, const double lon, const double lat, |
| 195 |
const idx_t index); |
| 196 |
void atlas__IndexKDTree__build(IndexKDTree::Implementation* This); |
| 197 |
void atlas__IndexKDTree__closestPoints(const IndexKDTree::Implementation* This, const double plon, const double plat, |
| 198 |
const size_t k, double*& lon, double*& lat, idx_t*& indices, double*& distances); |
| 199 |
void atlas__IndexKDTree__closestPoint(const IndexKDTree::Implementation* This, const double plon, const double plat, |
| 200 |
double& lon, double& lat, idx_t& index, double& distance); |
| 201 |
void atlas__IndexKDTree__closestPointsWithinRadius(const IndexKDTree::Implementation* This, const double plon, |
| 202 |
const double plat, const double radius, size_t& k, double*& lon, |
| 203 |
double*& lat, idx_t*& indices, double*& distances); |
| 204 |
const Geometry::Implementation* atlas__IndexKDTree__geometry(const IndexKDTree::Implementation* This); |
| 205 |
int atlas__IndexKDTree__empty(const IndexKDTree::Implementation* This); |
| 206 |
idx_t atlas__IndexKDTree__size(const IndexKDTree::Implementation* This); |
| 207 |
} |
| 208 |
|
| 209 |
//------------------------------------------------------------------------------------------------------ |
| 210 |
|
| 211 |
} // namespace util |
| 212 |
} // namespace atlas |