Debian Codegraph @

src/atlas/util/PolygonLocator.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 <algorithm>
14 #include <memory>
15 #include <sstream>
16
17 #include "atlas/library/config.h"
18 #include "atlas/projection/Projection.h"
19 #include "atlas/runtime/Exception.h"
20 #include "atlas/util/KDTree.h"
21 #include "atlas/util/Polygon.h"
22
23 #ifdef POLYGONLOCATOR_DEBUGGING
24 #include "atlas/runtime/Log.h"
25 #endif
26
27 namespace atlas {
28 namespace util {
29
30 //------------------------------------------------------------------------------------------------------
31
32 ///@brief Find polygon that contains a point
33 ///
34 /// Construction requires a list of polygons.
35 /// The implementation makes use of a KDTree that holds centroids of all polygons.
36 /// Once the nearest polygon-centroids (default=4) are found, the corresponding polygons are
37 /// visited in order of shortest distance, to check if the point is contained within.
38 class PolygonLocator {
39 public:
40 /// @brief Construct PolygonLocator from shared_ptr of polygons
41 PolygonLocator(const std::shared_ptr<const PolygonCoordinates::Vector> polygons,
42 const Projection& projection = Projection()):
43 shared_polygons_(polygons), polygons_(*shared_polygons_), projection_(projection) {
44 k_ = std::min(k_, polygons_.size());
45 buildKDTree();
46 }
47
48 /// @brief Construct PolygonLocator and move polygons inside.
49 PolygonLocator(PolygonCoordinates::Vector&& polygons, const Projection& projection = Projection()):
50 shared_polygons_(std::make_shared<PolygonCoordinates::Vector>(std::move(polygons))),
51 polygons_(*shared_polygons_),
52 projection_(projection) {
53 k_ = std::min(k_, polygons_.size());
54 buildKDTree();
55 }
56
57 /// @brief Construct PolygonLocator using reference to polygons.
58 /// !WARNING! polygons should not go out of scope before PolygonLocator
59 PolygonLocator(const PolygonCoordinates::Vector& polygons, const Projection& projection = Projection()):
60 polygons_(polygons), projection_(projection) {
61 k_ = std::min(k_, polygons_.size());
62 buildKDTree();
63 }
64
65 template <typename PointContainer, typename PolygonIndexContainer>
66 void operator()(const PointContainer& points, PolygonIndexContainer& index) {
67 ATLAS_ASSERT(points.size() == index.size());
68 typename PointContainer::const_iterator p = points.begin();
69 typename PointContainer::const_iterator p_end = points.end();
70 typename PolygonIndexContainer::iterator i = index.begin();
71 for (; p != p_end; ++p, ++i) {
72 *i = this->operator()(*p);
73 }
74 }
75
76 /// @brief find the polygon that holds the point (lon,lat)
77 idx_t operator()(const Point2& point) const {
78 const auto found = kdtree_.closestPoints(point, k_);
79 idx_t partition{-1};
80 for (size_t i = 0; i < found.size(); ++i) {
81 idx_t ii = found[i].payload();
82 #ifdef POLYGONLOCATOR_DEBUGGING
83 Log::info() << "Search point " << lonlat2xy(point) << " in polygon " << ii << ": ";
84 polygons_[ii].print(Log::info());
85 Log::info() << " ... ";
86 #endif
87 if (polygons_[ii].contains(lonlat2xy(point))) {
88 partition = ii;
89 #ifdef POLYGONLOCATOR_DEBUGGING
90 Log::info() << "FOUND" << std::endl;
91 #endif
92 break;
93 }
94 #ifdef POLYGONLOCATOR_DEBUGGING
95 Log::info() << "NOT_FOUND" << std::endl;
96 #endif
97 }
98
99 auto try_shifted_point = [&](double x) {
100 const Point2 shifted{x, point.y()};
101 const auto shifted_found = kdtree_.closestPoints(shifted, k_);
102 for (size_t i = 0; i < shifted_found.size(); ++i) {
103 idx_t ii = shifted_found[i].payload();
104 if (polygons_[ii].contains(lonlat2xy(shifted))) {
105 return ii;
106 }
107 }
108 return idx_t{-1};
109 };
110
111 if (partition < 0) {
112 partition = try_shifted_point(point.x() + 360.0);
113 }
114 if (partition < 0) {
115 partition = try_shifted_point(point.x() - 360.0);
116 }
117 if (partition < 0) {
118 std::stringstream out;
119 out << "Could not find find point {lon,lat} = " << point
120 << " or " << Point2{point.x() + 360.0, point.y()}
121 << " or " << Point2{point.x() - 360.0, point.y()}
122 << " in `k=" << k_ << "` \"nearest\" polygons [";
123 for (size_t i = 0; i < found.size(); ++i) {
124 if (i > 0) {
125 out << ", ";
126 }
127 out << found[i].payload();
128 }
129 out << "]. Increase `k`?";
130 throw_AssertionFailed(out.str(), Here());
131 }
132 return partition;
133 }
134
135 private:
136 void buildKDTree() {
137 kdtree_.reserve(polygons_.size());
138 for (idx_t p = 0; p < polygons_.size(); ++p) {
139 kdtree_.insert(xy2lonlat(polygons_[p].centroid()), p);
140 }
141 kdtree_.build();
142 }
143
144 Point2 lonlat2xy(const Point2& lonlat) const {
145 Point2 xy{lonlat};
146 projection_.lonlat2xy(xy.data());
147 return xy;
148 }
149 Point2 xy2lonlat(const Point2& xy) const {
150 Point2 lonlat{xy};
151 projection_.xy2lonlat(lonlat.data());
152 return lonlat;
153 }
154
155
156 std::shared_ptr<const PolygonCoordinates::Vector> shared_polygons_;
157 const PolygonCoordinates::Vector& polygons_;
158 Projection projection_;
159 idx_t k_{4};
160 IndexKDTree kdtree_;
161 };
162
163 //------------------------------------------------------------------------------------------------------
164
165 } // namespace util
166 } // namespace atlas