Debian Codegraph @

src/atlas/util/detail/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 <iosfwd>
14 #include <memory>
15
16 #include "eckit/container/KDTree.h"
17
18 #include "atlas/library/config.h"
19 #include "atlas/runtime/Exception.h"
20 #include "atlas/runtime/Log.h"
21 #include "atlas/util/Geometry.h"
22 #include "atlas/util/Object.h"
23 #include "atlas/util/Point.h"
24
25 namespace atlas {
26 namespace util {
27 namespace detail {
28
29 //------------------------------------------------------------------------------------------------------
30
31 // Abstract KDTree, intended to erase the internal KDTree type from eckit (Mapped or Memory)
32 // For usage, see atlas::util::KDTree
33 template <typename PayloadT, typename PointT = Point3>
34 class KDTreeBase : public Object {
35 #define ENABLE_IF_3D_AND_IS_LONLAT(POINT) \
36 typename = typename std::enable_if < PointT::DIMS == 3 && POINT::DIMS == 2 > ::type
37
38 private:
39 Geometry geometry_;
40
41 public:
42 using Payload = PayloadT;
43 using Point = PointT;
44 using PayloadList = std::vector<Payload>;
45
46 struct KDTreeTraits {
47 using Point = PointT;
48 using Payload = PayloadT;
49 };
50
51 struct Value {
52 using Point = typename KDTreeTraits::Point;
53 using Payload = typename KDTreeTraits::Payload;
54
55 template <typename Node>
56 Value(const Node& node): Value(node.point(), node.payload(), node.distance()) {}
57
58 Value(const Point& point, const Payload& payload): point_(point), payload_(payload) {}
59
60 Value(const Point& point, const Payload& payload, double distance):
61 point_(point), payload_(payload), distance_(distance) {}
62
63 const Point& point() const { return point_; }
64 const Payload& payload() const { return payload_; }
65 const double& distance() const { return distance_; }
66
67 private:
68 Point point_;
69 Payload payload_;
70 double distance_;
71 };
72
73 class ValueList : public std::vector<Value> {
74 public:
75 PayloadList payloads() const {
76 PayloadList list;
77 list.reserve(this->size());
78 for (auto& item : *this) {
79 list.emplace_back(item.payload());
80 }
81 return list;
82 }
83
84 template <typename NodeList>
85 ValueList(const NodeList& _list) {
86 this->reserve(_list.size());
87 for (const auto& item : _list) {
88 this->emplace_back(item);
89 }
90 }
91
92 void print(std::ostream& out) const {
93 out << "[";
94 for (size_t i = 0; i < this->size(); ++i) {
95 const auto& value = this->at(i);
96 out << "{payload:" << value.payload() << ",distance:" << value.distance() << ",point:" << value.point()
97 << "}";
98 if (i < this->size() - 1) {
99 out << ",";
100 }
101 }
102 out << "]";
103 }
104 friend std::ostream& operator<<(std::ostream& out, ValueList& This) {
105 This.print(out);
106 return out;
107 }
108 };
109
110
111 public:
112 KDTreeBase() = default;
113
114 KDTreeBase(const Geometry& geometry): geometry_(geometry) {}
115
116 virtual ~KDTreeBase() = default;
117
118 const Geometry& geometry() const { return geometry_; }
119
120 bool empty() const { return size() == 0; }
121
122 virtual idx_t size() const = 0;
123
124 virtual size_t footprint() const = 0;
125
126 /// @brief Reserve memory for building the kdtree in one shot (optional, at cost of extra memory)
127 /// Implementation depends in derived classes
128 virtual void reserve(idx_t /*size*/) {}
129
130 /// @brief Insert spherical point (lon,lat) or 3D cartesian point (x,y,z)
131 /// If memory has been reserved with reserve(), insertion will be delayed until build() is called.
132 template <typename Point>
133 void insert(const Point& p, const Payload& payload) {
134 do_insert(p, payload);
135 }
136
137 /// @brief Insert Value
138 /// If memory has been reserved with reserve(), insertion will be delayed until build() is called.
139 virtual void insert(const Value&) = 0;
140
141 /// @brief Build the kd-tree in one shot, if memory has been reserved, depending on derived class implementation
142 /// This will need to be called before all search functions like closestPoints().
143 virtual void build() {}
144
145 /// @brief Build the kd-tree in one shot
146 virtual void build(std::vector<Value>& values) = 0;
147
148 /// @brief Build with spherical points (lon,lat) where longitudes, latitudes, and payloads are separate containers.
149 /// Memory will be reserved with reserve() to match the size
150 template <typename Longitudes, typename Latitudes, typename Payloads>
151 void build(const Longitudes& longitudes, const Latitudes& latitudes, const Payloads& payloads) {
152 build(longitudes.begin(), longitudes.end(), latitudes.begin(), latitudes.end(), payloads.begin(),
153 payloads.end());
154 }
155
156 /// @brief Build with spherical points (lon,lat) given separate iterator ranges for longitudes, latitudes, and payloads.
157 /// Memory will be reserved with reserve() to match the size
158 template <typename LongitudesIterator, typename LatitudesIterator, typename PayloadsIterator>
159 void build(const LongitudesIterator& longitudes_begin, const LongitudesIterator& longitudes_end,
160 const LatitudesIterator& latitudes_begin, const LatitudesIterator& latitudes_end,
161 const PayloadsIterator& payloads_begin, const PayloadsIterator& payloads_end) {
162 reserve(std::distance(payloads_begin, payloads_end));
163 auto lon = longitudes_begin;
164 auto lat = latitudes_begin;
165 auto payload = payloads_begin;
166 for (; lon != longitudes_end && lat != latitudes_end && payload != payloads_end; lon++, lat++, payload++) {
167 insert(Point2{*lon, *lat}, *payload);
168 }
169 ATLAS_ASSERT(lon == longitudes_end);
170 ATLAS_ASSERT(lat == latitudes_end);
171 ATLAS_ASSERT(payload == payloads_end);
172 build();
173 }
174
175 /// @brief Build with spherical points (lon,lat) where longitudes, latitudes, and payloads are separate containers.
176 /// Memory will be reserved with reserve() to match the size
177 template <typename Points, typename Payloads>
178 void build(const Points& points, const Payloads& payloads) {
179 build(points.begin(), points.end(), payloads.begin(), payloads.end());
180 }
181
182 /// @brief Build with spherical points (lon,lat) given separate iterator ranges for longitudes, latitudes, and payloads.
183 /// Memory will be reserved with reserve() to match the size
184 template <typename PointIterator, typename PayloadsIterator>
185 void build(const PointIterator& points_begin, const PointIterator& points_end,
186 const PayloadsIterator& payloads_begin, const PayloadsIterator& payloads_end) {
187 reserve(std::distance(points_begin, points_end));
188 PointIterator point = points_begin;
189 PayloadsIterator payload = payloads_begin;
190 for (; point != points_end && payload != payloads_end; ++point, ++payload) {
191 insert(*point, *payload);
192 }
193 ATLAS_ASSERT(point == points_end);
194 ATLAS_ASSERT(payload == payloads_end);
195 build();
196 }
197
198
199 /// @brief Find k nearest neighbours given a 3D cartesian point (x,y,z) or 2D lonlat point(lon,lat)
200 template <typename Point>
201 ValueList closestPoints(const Point& p, size_t k) const {
202 return do_closestPoints(p, k);
203 }
204
205 /// @brief Find nearest neighbour given a 3D cartesian point (x,y,z)
206 template <typename Point>
207 Value closestPoint(const Point& p) const {
208 return do_closestPoint(p);
209 }
210
211 /// @brief Find all points within a distance of given radius from a given point (x,y,z)
212 template <typename Point>
213 ValueList closestPointsWithinRadius(const Point& p, double radius) const {
214 return do_closestPointsWithinRadius(p, radius);
215 }
216
217 private:
218 /// @brief Insert spherical point (lon,lat)
219 /// If memory has been reserved with reserve(), insertion will be delayed until build() is called.
220 void do_insert(const Point& p, const Payload& payload) { insert(Value{p, payload}); }
221
222
223 /// @brief Insert spherical point (lon,lat)
224 /// If memory has been reserved with reserve(), insertion will be delayed until build() is called.
225 template <typename LonLat, ENABLE_IF_3D_AND_IS_LONLAT(LonLat)>
226 void do_insert(const LonLat& p, const Payload& payload) {
227 do_insert(make_Point(p), payload);
228 }
229
230 /// @brief Find k nearest neighbours given a 3D cartesian point (x,y,z)
231 virtual ValueList do_closestPoints(const Point&, size_t k) const = 0;
232
233 /// @brief Find nearest neighbour given a 3D cartesian point (x,y,z)
234 virtual Value do_closestPoint(const Point&) const = 0;
235
236 /// @brief Find all points within a distance of given radius from a given point (x,y,z)
237 virtual ValueList do_closestPointsWithinRadius(const Point&, double radius) const = 0;
238
239
240 /// @brief Find k nearest neighbour given a 2D lonlat point (lon,lat)
241 template <typename LonLat, ENABLE_IF_3D_AND_IS_LONLAT(LonLat)>
242 ValueList do_closestPoints(const LonLat& p, size_t k) const {
243 return do_closestPoints(make_Point(p), k);
244 }
245
246 /// @brief Find nearest neighbour given a 2D lonlat point (lon,lat)
247 template <typename LonLat, ENABLE_IF_3D_AND_IS_LONLAT(LonLat)>
248 Value do_closestPoint(const LonLat& p) const {
249 return do_closestPoint(make_Point(p));
250 }
251
252 /// @brief Find all points within a distance of given radius from a given point (lon,lat)
253 template <typename LonLat, ENABLE_IF_3D_AND_IS_LONLAT(LonLat)>
254 ValueList do_closestPointsWithinRadius(const LonLat& p, double radius) const {
255 return do_closestPointsWithinRadius(make_Point(p), radius);
256 }
257
258 template <typename LonLat, ENABLE_IF_3D_AND_IS_LONLAT(LonLat)>
259 Point make_Point(const LonLat& lonlat) const {
260 static_assert(std::is_base_of<Point2, LonLat>::value, "LonLat must be derived from Point2");
261 static_assert(std::is_base_of<Point3, Point>::value, "Point must be derived from Point3");
262 Point xyz;
263 geometry().lonlat2xyz(lonlat, xyz);
264 return xyz;
265 }
266 #undef ENABLE_IF_3D_AND_IS_LONLAT
267 };
268
269 //------------------------------------------------------------------------------------------------------
270 // Concrete implementation
271
272 template <typename TreeT, typename PayloadT = typename TreeT::Payload, typename PointT = typename TreeT::Point>
273 class KDTree_eckit : public KDTreeBase<PayloadT, PointT> {
274 using Tree = TreeT;
275 using Base = KDTreeBase<PayloadT, PointT>;
276
277 public:
278 using Point = typename Base::Point;
279 using Payload = typename Base::Payload;
280 using PayloadList = typename Base::PayloadList;
281 using Value = typename Base::Value;
282 using ValueList = typename Base::ValueList;
283
284 using Base::build;
285 using Base::closestPoint;
286 using Base::closestPoints;
287 using Base::closestPointsWithinRadius;
288 using Base::insert;
289 using Base::reserve;
290
291 public:
292 template <typename... Args>
293 KDTree_eckit(const Geometry& geometry, Args... args):
294 KDTreeBase<Payload, Point>(geometry), tree_(new Tree(args...)) {
295 static_asserts();
296 }
297
298
299 template <typename... Args>
300 KDTree_eckit(Args... args): tree_(new Tree(args...)) {
301 static_asserts();
302 }
303
304 KDTree_eckit(const std::shared_ptr<Tree>& tree): tree_(tree) { static_asserts(); }
305
306 KDTree_eckit(const std::shared_ptr<Tree>& tree, const Geometry& geometry):
307 KDTreeBase<Payload, Point>(geometry), tree_(tree) {
308 static_asserts();
309 }
310
311 idx_t size() const override {
312 #if ATLAS_ECKIT_VERSION_AT_LEAST(1, 13, 2)
313 return static_cast<idx_t>(tree_->size());
314 #else
315 // Assume ECKIT-515 not implemented.
316 // Very bad implementation, with a workaround for empty tree
317 idx_t size{0};
318 try {
319 for (const auto& item : *tree_) {
320 size++;
321 }
322 }
323 catch (const eckit::AssertionFailed&) {
324 }
325 return size;
326 #endif
327 }
328
329 size_t footprint() const override { return size() * sizeof(typename Tree::Node); }
330
331 void reserve(idx_t size) override;
332
333 void build() override;
334
335 void build(std::vector<Value>&) override;
336
337 /// @brief Insert 3D cartesian point (x,y,z)
338 /// If memory has been reserved with reserve(), insertion will be delayed until build() is called.
339 void insert(const Value& value) override;
340
341 /// @brief Find k nearest neighbours given a 3D cartesian point (x,y,z)
342 ValueList do_closestPoints(const Point&, size_t k) const override;
343
344 /// @brief Find nearest neighbour given a 3D cartesian point (x,y,z)
345 Value do_closestPoint(const Point&) const override;
346
347 /// @brief Find all points within a distance of given radius from a given point (x,y,z)
348 ValueList do_closestPointsWithinRadius(const Point&, double radius) const override;
349
350 const Tree& tree() const { return *tree_; }
351
352 private:
353 void assert_built() const;
354
355 static void static_asserts() {
356 static_assert(std::is_convertible<typename Tree::Payload, Payload>::value,
357 "Tree::Payload must be convertible this Payload type");
358 static_assert(std::is_convertible<typename Tree::Point, Point>::value,
359 "Tree::Point must be convertible to this Point type");
360 }
361
362 private:
363 std::vector<Value> tmp_;
364 mutable std::shared_ptr<Tree> tree_; // mutable because its member functions are non-const...
365 };
366
367 //------------------------------------------------------------------------------------------------------
368
369 template <typename Payload, typename Point>
370 using KDTreeMemory = KDTree_eckit<typename eckit::KDTreeMemory<typename KDTreeBase<Payload, Point>::KDTreeTraits>>;
371
372 //------------------------------------------------------------------------------------------------------
373
374 template <typename TreeT, typename PayloadT, typename PointT>
375 void KDTree_eckit<TreeT, PayloadT, PointT>::reserve(idx_t size) {
376 tmp_.reserve(size);
377 }
378
379
380 template <typename TreeT, typename PayloadT, typename PointT>
381 void KDTree_eckit<TreeT, PayloadT, PointT>::insert(const Value& value) {
382 if (tmp_.capacity()) {
383 tmp_.emplace_back(value);
384 }
385 else {
386 tree_->insert(value);
387 }
388 }
389
390 template <typename TreeT, typename PayloadT, typename PointT>
391 void KDTree_eckit<TreeT, PayloadT, PointT>::build() {
392 if (tmp_.size()) {
393 build(tmp_);
394 tmp_.clear();
395 tmp_.shrink_to_fit();
396 }
397 }
398
399 template <typename TreeT, typename PayloadT, typename PointT>
400 void KDTree_eckit<TreeT, PayloadT, PointT>::build(std::vector<Value>& values) {
401 tree_->build(values);
402 }
403
404
405 template <typename TreeT, typename PayloadT, typename PointT>
406 typename KDTree_eckit<TreeT, PayloadT, PointT>::ValueList KDTree_eckit<TreeT, PayloadT, PointT>::do_closestPoints(
407 const Point& p, size_t k) const {
408 assert_built();
409 return tree_->kNearestNeighbours(p, k);
410 }
411
412 template <typename TreeT, typename PayloadT, typename PointT>
413 typename KDTree_eckit<TreeT, PayloadT, PointT>::Value KDTree_eckit<TreeT, PayloadT, PointT>::do_closestPoint(
414 const Point& p) const {
415 assert_built();
416 return tree_->nearestNeighbour(p);
417 }
418
419 template <typename TreeT, typename PayloadT, typename PointT>
420 typename KDTree_eckit<TreeT, PayloadT, PointT>::ValueList
421 KDTree_eckit<TreeT, PayloadT, PointT>::do_closestPointsWithinRadius(const Point& p, double radius) const {
422 assert_built();
423 return tree_->findInSphere(p, radius);
424 }
425
426 template <typename TreeT, typename PayloadT, typename PointT>
427 void KDTree_eckit<TreeT, PayloadT, PointT>::assert_built() const {
428 if (tmp_.capacity()) {
429 throw_AssertionFailed("KDTree was used before calling build()");
430 }
431 }
432
433 //------------------------------------------------------------------------------------------------------
434
435 } // namespace detail
436 } // namespace util
437 } // namespace atlas