Debian Codegraph @

src/atlas/util/PolygonXY.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
12 #include <algorithm>
13 #include <cmath>
14 #include <iostream>
15 #include <limits>
16
17 #include "atlas/domain/Domain.h"
18 #include "atlas/runtime/Exception.h"
19 #include "atlas/runtime/Log.h"
20 #include "atlas/util/CoordinateEnums.h"
21 #include "atlas/util/PolygonXY.h"
22
23 namespace atlas {
24 namespace util {
25
26 //------------------------------------------------------------------------------------------------------
27
28 namespace {
29
30 double cross_product_analog(const Point2& A, const Point2& B, const Point2& C) {
31 return (A.x() - C.x()) * (B.y() - C.y()) - (A.y() - C.y()) * (B.x() - C.x());
32 }
33
34
35 template <typename PointContainer>
36 PointLonLat compute_centroid(const PointContainer& points) {
37 ATLAS_ASSERT(eckit::geometry::points_equal(points.front(), points.back()));
38
39 PointLonLat centroid = {0, 0};
40 double signed_area = 0.;
41 double a = 0.; // Partial signed area
42
43 for (size_t i = 0; i < points.size() - 1; ++i) {
44 const Point2& p0 = points[i];
45 const Point2& p1 = points[i + 1];
46 a = p0[0] * p1[1] - p1[0] * p0[1];
47 signed_area += a;
48 centroid[0] += (p0[0] + p1[0]) * a;
49 centroid[1] += (p0[1] + p1[1]) * a;
50 }
51 signed_area *= 0.5;
52 centroid[0] /= (6. * signed_area);
53 centroid[1] /= (6. * signed_area);
54
55 return centroid;
56 }
57
58 template <typename PointContainer>
59 double compute_inner_radius_squared(const PointContainer& points, const PointLonLat& centroid) {
60 auto distance2 = [](const Point2& a, const Point2& b) {
61 double dx = (a[0] - b[0]);
62 double dy = (a[1] - b[1]);
63 return dx * dx + dy * dy;
64 };
65 auto dot = [](const Point2& a, const Point2& b) { return a[0] * b[0] + a[1] * b[1]; };
66 double R2 = std::numeric_limits<double>::max();
67 Point2 projection;
68 for (size_t i = 0; i < points.size() - 1; ++i) {
69 double d2 = distance2(points[i], points[i + 1]);
70 double t = std::max(0., std::min(1., dot(centroid - points[i], points[i + 1] - points[i]) / d2));
71 projection[0] = points[i][0] + t * (points[i + 1][0] - points[i][0]);
72 projection[1] = points[i][1] + t * (points[i + 1][1] - points[i][1]);
73 R2 = std::min(R2, distance2(projection, centroid));
74 //Log::info() << "Segment " << points[i] << " - " << points[i+1] << " : projection = " << projection << " \t distance = " << std::sqrt(distance2(projection,centroid) ) << std::endl;
75 }
76 return R2;
77 }
78
79 } // namespace
80
81 //------------------------------------------------------------------------------------------------------
82
83 PolygonXY::PolygonXY(const PartitionPolygon& partition_polygon): PolygonCoordinates(partition_polygon.xy(), true) {
84 const auto& inscribed = partition_polygon.inscribedDomain();
85 if( inscribed.xmin() != inscribed.xmax() && inscribed.ymin() != inscribed.ymax() ) {
86 inner_coordinatesMin_ = {inscribed.xmin(), inscribed.ymin()};
87 inner_coordinatesMax_ = {inscribed.xmax(), inscribed.ymax()};
88 }
89 else {
90 centroid_ = compute_centroid(coordinates_);
91 inner_radius_squared_ = compute_inner_radius_squared(coordinates_, centroid_);
92
93 ATLAS_ASSERT(PolygonXY::contains(centroid_));
94 }
95 }
96
97 bool PolygonXY::contains(const Point2& P) const {
98 auto distance2 = [](const Point2& p, const Point2& centroid) {
99 double dx = (p[0] - centroid[0]);
100 double dy = (p[1] - centroid[1]);
101 return dx * dx + dy * dy;
102 };
103
104 constexpr double eps = 1.e-10;
105 // check first bounding box
106 if (coordinatesMax_.y() + eps < P.y() || P.y() < coordinatesMin_.y() - eps || coordinatesMax_.x() + eps < P.x() ||
107 P.x() < coordinatesMin_.x() - eps) {
108 return false;
109 }
110
111 if (inner_radius_squared_ == 0) { // check inner bounding box
112 if (inner_coordinatesMin_.x() <= P.x() && P.x() <= inner_coordinatesMax_.x() &&
113 inner_coordinatesMin_.y() <= P.y() && P.y() <= inner_coordinatesMax_.y()) {
114 return true;
115 }
116 }
117 else { // check inscribed circle
118 if (distance2(P, centroid_) < inner_radius_squared_) {
119 return true;
120 }
121 }
122
123 // winding number
124 int wn = 0;
125
126 // loop on polygon edges
127 for (size_t i = 1; i < coordinates_.size(); ++i) {
128 const Point2& A = coordinates_[i - 1];
129 const Point2& B = coordinates_[i];
130
131 // check point-edge side and direction, using 2D-analog cross-product;
132 // tests if P is left|on|right of a directed A-B infinite line, by
133 // intersecting either:
134 // - "up" on upward crossing & P left of edge, or
135 // - "down" on downward crossing & P right of edge
136 const bool APB = (A.y() <= P.y() && P.y() <= B.y());
137 const bool BPA = (B.y() <= P.y() && P.y() <= A.y());
138
139 if (APB != BPA) {
140 const double side = cross_product_analog(P, A, B);
141 bool on_edge = std::abs(side) < eps;
142 if (on_edge) {
143 return true;
144 }
145 if (APB && side > 0) {
146 ++wn;
147 }
148 else if (BPA && side < 0) {
149 --wn;
150 }
151 }
152 }
153
154 // wn == 0 only when P is outside
155 return wn != 0;
156 }
157
158 //------------------------------------------------------------------------------------------------------
159
160 } // namespace util
161 } // namespace atlas