Debian Codegraph @

src/atlas/util/Polygon.cc

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 #include <algorithm>
12 #include <cmath>
13 #include <iostream>
14 #include <limits>
15 #include <sstream>
16
17 #include "eckit/types/FloatCompare.h"
18
19 #include "atlas/domain/Domain.h"
20 #include "atlas/projection/Projection.h"
21 #include "atlas/runtime/Exception.h"
22 #include "atlas/util/CoordinateEnums.h"
23 #include "atlas/util/Polygon.h"
24
25 namespace atlas {
26 namespace util {
27
28 namespace {
29
30 //------------------------------------------------------------------------------------------------------
31
32 double cross_product_analog(const Point2& A, const Point2& B, const Point2& C) {
33 return (A[XX] - C[XX]) * (B[YY] - C[YY]) - (A[YY] - C[YY]) * (B[XX] - C[XX]);
34 }
35
36 } // namespace
37
38 //------------------------------------------------------------------------------------------------------
39
40 Polygon::Polygon() = default;
41
42 Polygon::Polygon(const Polygon::edge_set_t& edges) {
43 setup(edges);
44 }
45
46 void Polygon::setup(const Polygon::edge_set_t& edges) {
47 if (edges.empty()) {
48 return;
49 }
50
51 // get external edges by attempting to remove reversed edges, if any
52 edge_set_t extEdges;
53 for (const edge_t& e : edges) {
54 if (!extEdges.erase(e.reverse())) {
55 extEdges.insert(e);
56 }
57 }
58 ATLAS_ASSERT(extEdges.size() >= 2);
59
60 // set one polygon cycle, by picking next edge with first node same as second
61 // node of last edge
62 clear();
63 reserve(extEdges.size() + 1);
64
65 emplace_back(extEdges.begin()->first);
66 for (edge_set_t::iterator e = extEdges.begin(); e != extEdges.end() && e->first == back();
67 e = extEdges.lower_bound(edge_t(back(), std::numeric_limits<idx_t>::min()))) {
68 emplace_back(e->second);
69 extEdges.erase(*e);
70 }
71 ATLAS_ASSERT(front() == back());
72
73 // exhaust remaining edges, should represent additional cycles, if any
74 while (!extEdges.empty()) {
75 operator+=(Polygon(extEdges));
76 }
77 }
78
79 Polygon::operator bool() const {
80 return !Polygon::empty();
81 }
82
83 Polygon& Polygon::operator+=(const Polygon& other) {
84 if (empty()) {
85 return operator=(other);
86 }
87
88 // polygon can have multiple cycles, but must be connected graphs
89 // Note: a 'cycle' is handled by repeating the indices, excluding (repeated)
90 // last index
91 ATLAS_ASSERT(other.front() == other.back());
92 const difference_type N = difference_type(other.size()) - 1;
93
94 container_t cycle(2 * size_t(N));
95 std::copy(other.begin(), other.begin() + N, cycle.begin());
96 std::copy(other.begin(), other.begin() + N, cycle.begin() + N);
97
98 for (const_iterator c = cycle.begin(); c != cycle.begin() + N; ++c) {
99 iterator here = std::find(begin(), end(), *c);
100 if (here != end()) {
101 insert(here, c, c + N);
102 return *this;
103 }
104 }
105
106 throw_AssertionFailed("Polygon: could not merge polygons, they are not connected", Here());
107 }
108
109 void Polygon::print(std::ostream& s) const {
110 char z = '{';
111 for (auto n : static_cast<const container_t&>(*this)) {
112 s << z << n;
113 z = ',';
114 }
115 s << '}';
116 }
117
118 const PartitionPolygon::RectangleXY& PartitionPolygon::inscribedDomain() const {
119 static RectangleXY inscribed;
120 return inscribed;
121 }
122
123 //------------------------------------------------------------------------------------------------------
124
125 PolygonCoordinates::PolygonCoordinates(const Polygon& poly, const double x[], const double y[], size_t xstride, size_t ystride, bool removeAlignedPoints) {
126 ATLAS_ASSERT(poly.size() > 2);
127 ATLAS_ASSERT(poly.front() == poly.back());
128
129 // Point coordinates
130 // - use a bounding box to quickly discard points,
131 // - except when that is above/below bounding box but poles should be included
132
133 coordinates_.clear();
134 coordinates_.reserve(poly.size());
135
136 coordinatesMin_ = Point2(x[poly[0]], y[poly[0]]);
137 coordinatesMax_ = coordinatesMin_;
138
139 size_t nb_removed_points_due_to_alignment = 0;
140
141
142 for (size_t i = 0; i < poly.size(); ++i) {
143 Point2 A(x[poly[i*xstride]], y[poly[i*ystride]]);
144 coordinatesMin_ = Point2::componentsMin(coordinatesMin_, A);
145 coordinatesMax_ = Point2::componentsMax(coordinatesMax_, A);
146
147 // if new point is aligned with existing edge (cross product ~= 0) make the
148 // edge longer
149 if ((coordinates_.size() >= 2) && removeAlignedPoints) {
150 const Point2& B = coordinates_.back();
151 const Point2& C = coordinates_[coordinates_.size() - 2];
152 if (eckit::types::is_approximately_equal(0., cross_product_analog(A, B, C), 1.e-10)) {
153 coordinates_.back() = A;
154 ++nb_removed_points_due_to_alignment;
155 continue;
156 }
157 }
158
159 coordinates_.emplace_back(A);
160 }
161
162 ATLAS_ASSERT(coordinates_.size() == poly.size() - nb_removed_points_due_to_alignment);
163 }
164
165
166 template <typename PointContainer>
167 PolygonCoordinates::PolygonCoordinates(const PointContainer& points) {
168 coordinates_.assign(points.begin(), points.end());
169 ATLAS_ASSERT(coordinates_.size() > 2);
170 ATLAS_ASSERT(eckit::geometry::points_equal(coordinates_.front(), coordinates_.back()));
171
172 coordinatesMin_ = coordinates_.front();
173 coordinatesMax_ = coordinatesMin_;
174 centroid_ = Point2{0., 0.};
175 for (const Point2& P : coordinates_) {
176 coordinatesMin_ = Point2::componentsMin(coordinatesMin_, P);
177 coordinatesMax_ = Point2::componentsMax(coordinatesMax_, P);
178 centroid_[XX] += P[XX];
179 centroid_[YY] += P[YY];
180 }
181 centroid_[XX] /= coordinates_.size();
182 centroid_[YY] /= coordinates_.size();
183 }
184
185 template <typename PointContainer>
186 PolygonCoordinates::PolygonCoordinates(const PointContainer& points, bool removeAlignedPoints) {
187 coordinates_.clear();
188 coordinates_.reserve(points.size());
189
190 coordinatesMin_ = Point2{std::numeric_limits<double>::max(), std::numeric_limits<double>::max()};
191 coordinatesMax_ = Point2{std::numeric_limits<double>::lowest(), std::numeric_limits<double>::lowest()};
192 centroid_ = Point2{0., 0.};
193
194 for (size_t i = 0; i < points.size(); ++i) {
195 const Point2& A = points[i];
196 coordinatesMin_ = Point2::componentsMin(coordinatesMin_, A);
197 coordinatesMax_ = Point2::componentsMax(coordinatesMax_, A);
198 centroid_[XX] += A[XX];
199 centroid_[YY] += A[YY];
200
201 // if new point is aligned with existing edge (cross product ~= 0) make the
202 // edge longer
203 if ((coordinates_.size() >= 2) && removeAlignedPoints) {
204 const Point2& B = coordinates_.back();
205 const Point2& C = coordinates_[coordinates_.size() - 2];
206 if (eckit::types::is_approximately_equal(0., cross_product_analog(A, B, C), 1.e-10)) {
207 coordinates_.back() = A;
208 continue;
209 }
210 }
211 coordinates_.emplace_back(A);
212 }
213 centroid_[XX] /= points.size();
214 centroid_[YY] /= points.size();
215
216 ATLAS_ASSERT(coordinates_.size() > 2);
217 ATLAS_ASSERT(eckit::geometry::points_equal(coordinates_.front(), coordinates_.back()));
218 }
219
220 template PolygonCoordinates::PolygonCoordinates(const std::vector<Point2>&);
221 template PolygonCoordinates::PolygonCoordinates(const std::vector<PointXY>&);
222 template PolygonCoordinates::PolygonCoordinates(const std::vector<PointLonLat>&);
223
224 template PolygonCoordinates::PolygonCoordinates(const std::vector<Point2>&, bool);
225 template PolygonCoordinates::PolygonCoordinates(const std::vector<PointXY>&, bool);
226 template PolygonCoordinates::PolygonCoordinates(const std::vector<PointLonLat>&, bool);
227
228
229 PolygonCoordinates::~PolygonCoordinates() = default;
230
231 const Point2& PolygonCoordinates::coordinatesMax() const {
232 return coordinatesMax_;
233 }
234
235 const Point2& PolygonCoordinates::coordinatesMin() const {
236 return coordinatesMin_;
237 }
238
239 const Point2& PolygonCoordinates::centroid() const {
240 return centroid_;
241 }
242
243 void PolygonCoordinates::print(std::ostream& out) const {
244 out << "[";
245 for (size_t i = 0; i < coordinates_.size(); ++i) {
246 if (i > 0) {
247 out << " ";
248 }
249 out << coordinates_[i];
250 }
251 out << "]";
252 }
253
254 std::ostream& operator<<(std::ostream& out, const PolygonCoordinates& pc) {
255 pc.print(out);
256 return out;
257 }
258
259 Polygon::edge_set_t ExplicitPartitionPolygon::compute_edges(idx_t points_size) {
260 util::Polygon::edge_set_t edges;
261 if (points_size > 0) {
262 auto add_edge = [&](idx_t p1, idx_t p2) {
263 util::Polygon::edge_t edge = {p1, p2};
264 edges.insert(edge);
265 // Log::info() << edge.first << " " << edge.second << std::endl;
266 };
267 for (idx_t p = 0; p < points_size - 2; ++p) {
268 add_edge(p, p + 1);
269 }
270 add_edge(points_size - 2, 0);
271 }
272 return edges;
273 }
274
275 void ExplicitPartitionPolygon::allGather(PartitionPolygons&) const {
276 ATLAS_NOTIMPLEMENTED;
277 }
278
279 std::string PartitionPolygons::json(const eckit::Configuration& config) const {
280 std::ostringstream out;
281 out << "[\n";
282 for (size_t i=0; i<size(); ++i) {
283 out << at(i).json(config);
284 if (i<size()-1) {
285 out << ",\n";
286 }
287 }
288 out << "\n]";
289 return out.str();
290 }
291
292
293 std::string PartitionPolygon::json(const eckit::Configuration& ) const {
294 auto points = xy();
295 std::ostringstream out;
296 out << "[";
297 for (size_t i=0; i<points.size(); ++i) {
298 auto& p = points[i];
299 out << "["<< p[0] << "," << p[1] << "]";
300 if (i<points.size()-1) {
301 out << ",";
302 }
303 }
304 out << "]";
305 return out.str();
306 }
307
308 //------------------------------------------------------------------------------------------------------
309
310 } // namespace util
311 } // namespace atlas