Debian Codegraph @

src/atlas/util/KDTree.h

raw
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