| 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 <vector> |
| 14 |
|
| 15 |
#include "eckit/deprecated.h" |
| 16 |
|
| 17 |
#include "atlas/util/Point.h" |
| 18 |
#include "atlas/util/Polygon.h" |
| 19 |
#include "atlas/runtime/Log.h" |
| 20 |
|
| 21 |
#define DEBUG_OUTPUT 0 |
| 22 |
|
| 23 |
namespace atlas { |
| 24 |
namespace util { |
| 25 |
|
| 26 |
//------------------------------------------------------------------------------------------------------ |
| 27 |
|
| 28 |
class ConvexSphericalPolygon { |
| 29 |
public: |
| 30 |
static constexpr int MAX_GRIDCELL_EDGES = 4; |
| 31 |
static constexpr int MAX_SIZE = 2 * MAX_GRIDCELL_EDGES + 1; |
| 32 |
|
| 33 |
public: |
| 34 |
class GreatCircleSegment { |
| 35 |
public: |
| 36 |
GreatCircleSegment(const PointXYZ& p1, const PointXYZ& p2): p1_(p1), p2_(p2), cross_(PointXYZ::cross(p1, p2)) {} |
| 37 |
|
| 38 |
// For a given segment, the "left" hemisphere is defined on the left of the segment when walking from first() to second() |
| 39 |
inline bool inLeftHemisphere(const PointXYZ& P, const double offset = 0., std::ostream* out = NULL) const { |
| 40 |
#if DEBUG_OUTPUT |
| 41 |
if (out) { |
| 42 |
*out << " inLeftHemi: " <<PointXYZ::dot(cross(), P) << " >= " << offset << " ? " |
| 43 |
<< (PointXYZ::dot(cross(), P) >= offset) << std::endl; |
| 44 |
} |
| 45 |
#endif |
| 46 |
return (cross_[0] * P[0] + cross_[1] * P[1] + cross_[2] * P[2]) >= offset; // has to have = included |
| 47 |
} |
| 48 |
|
| 49 |
PointXYZ intersect(const GreatCircleSegment&, std::ostream* f = NULL, double pointsSameEPS = std::numeric_limits<double>::epsilon()) const; |
| 50 |
|
| 51 |
const PointXYZ& first() const { return p1_; } |
| 52 |
|
| 53 |
const PointXYZ& second() const { return p2_; } |
| 54 |
|
| 55 |
const PointXYZ& cross() const { return cross_; } |
| 56 |
|
| 57 |
private: |
| 58 |
const PointXYZ p1_; |
| 59 |
const PointXYZ p2_; |
| 60 |
const PointXYZ cross_; |
| 61 |
}; |
| 62 |
|
| 63 |
public: |
| 64 |
ConvexSphericalPolygon() = default; |
| 65 |
|
| 66 |
template <class Points> |
| 67 |
using contains_PointLonLat = std::is_same<typename std::decay<typename Points::value_type>::type, PointLonLat>; |
| 68 |
|
| 69 |
template <class Points, typename std::enable_if<contains_PointLonLat<Points>::value, void>::type* = nullptr> |
| 70 |
ConvexSphericalPolygon(const Points& points): ConvexSphericalPolygon(points.data(), points.size()) {} |
| 71 |
|
| 72 |
ConvexSphericalPolygon(const PointLonLat points[], size_t size); |
| 73 |
|
| 74 |
ConvexSphericalPolygon(const PointXYZ& p1, const PointXYZ& p2, const PointXYZ& p3): |
| 75 |
ConvexSphericalPolygon(std::array<PointXYZ, 3>{p1, p2, p3}.data(), 3) {} |
| 76 |
|
| 77 |
ConvexSphericalPolygon(const PointXYZ points[], size_t size); |
| 78 |
|
| 79 |
void invalidate_this_polygon() { |
| 80 |
size_ = 0; |
| 81 |
valid_ = false; |
| 82 |
area_ = 0.; |
| 83 |
} |
| 84 |
|
| 85 |
operator bool() const { return valid_; } |
| 86 |
|
| 87 |
size_t size() const { return size_; } |
| 88 |
|
| 89 |
const std::vector<PointXYZ>& edge_normals() const { |
| 90 |
if (not computed_edge_normals_) { |
| 91 |
compute_edge_normals(); |
| 92 |
} |
| 93 |
return edge_normals_; |
| 94 |
} |
| 95 |
|
| 96 |
double area() const { |
| 97 |
if (not computed_area_) { |
| 98 |
compute_centroid_and_area(); |
| 99 |
} |
| 100 |
return area_; |
| 101 |
} |
| 102 |
|
| 103 |
const PointXYZ& centroid() const { |
| 104 |
if (not computed_centroid_) { |
| 105 |
compute_centroid_and_area(); |
| 106 |
} |
| 107 |
return centroid_; |
| 108 |
} |
| 109 |
|
| 110 |
double radius() const { |
| 111 |
if (not computed_radius_) { |
| 112 |
radius_ = compute_radius(); |
| 113 |
computed_radius_ = true; |
| 114 |
} |
| 115 |
return radius_; |
| 116 |
} |
| 117 |
|
| 118 |
ConvexSphericalPolygon intersect(const ConvexSphericalPolygon& pol, std::ostream* f = nullptr, double pointsEqualEPS = std::numeric_limits<double>::epsilon()) const; |
| 119 |
|
| 120 |
/* |
| 121 |
* @brief check if two spherical polygons area equal |
| 122 |
* @param[in] P given point in (x,y,z) coordinates |
| 123 |
* @return true if equal vertices |
| 124 |
*/ |
| 125 |
bool equals(const ConvexSphericalPolygon& plg, const double deg_prec = 1e-10) const; |
| 126 |
|
| 127 |
void print(std::ostream&) const; |
| 128 |
|
| 129 |
std::string json(int precision = 0) const; |
| 130 |
|
| 131 |
friend std::ostream& operator<<(std::ostream& out, const ConvexSphericalPolygon& p) { |
| 132 |
p.print(out); |
| 133 |
return out; |
| 134 |
} |
| 135 |
|
| 136 |
const PointXYZ& operator[](idx_t n) const { return sph_coords_[n]; } |
| 137 |
|
| 138 |
int next(const int index) const { return (index == size_ - 1) ? 0 : index + 1; }; |
| 139 |
|
| 140 |
int previous(const int index) const { return (index == 0) ? size_ - 1 : index - 1; }; |
| 141 |
|
| 142 |
int compute_vertex_weights(const PointXYZ& candidatePoint, double vertex_weights[], size_t vertex_weights_size); |
| 143 |
|
| 144 |
static void fpe(bool v) { fpe_ = v; } |
| 145 |
static bool fpe() { return fpe_; } |
| 146 |
private: |
| 147 |
struct SubTriangle { |
| 148 |
PointXYZ centroid; |
| 149 |
double area; |
| 150 |
}; |
| 151 |
struct SubTriangles : public std::array<SubTriangle, MAX_SIZE> { |
| 152 |
public: |
| 153 |
size_t size() const { return size_; } |
| 154 |
size_t& size() { return size_; } |
| 155 |
double area() const; |
| 156 |
std::array<SubTriangle, MAX_SIZE>::const_iterator end() const { return data() + size_; } |
| 157 |
|
| 158 |
private: |
| 159 |
size_t size_{0}; |
| 160 |
}; |
| 161 |
|
| 162 |
void compute_centroid_and_area() const; |
| 163 |
|
| 164 |
double compute_radius() const; |
| 165 |
|
| 166 |
SubTriangles triangulate() const; |
| 167 |
|
| 168 |
template <class ClippedCoords> |
| 169 |
void clip(const GreatCircleSegment&, ClippedCoords&, const double& pointsSameEPS = std::numeric_limits<double>::epsilon(), std::ostream* out = nullptr); |
| 170 |
|
| 171 |
// Set valid_ to true when polygon is convex |
| 172 |
void validate(); |
| 173 |
|
| 174 |
void compute_edge_normals() const; |
| 175 |
|
| 176 |
private: |
| 177 |
std::array<PointXYZ, MAX_SIZE> sph_coords_; |
| 178 |
mutable PointXYZ centroid_; |
| 179 |
mutable double area_{0}; |
| 180 |
mutable double radius_{0}; |
| 181 |
size_t size_{0}; |
| 182 |
bool valid_{false}; |
| 183 |
mutable bool computed_centroid_{false}; |
| 184 |
mutable bool computed_radius_{false}; |
| 185 |
mutable bool computed_area_{false}; |
| 186 |
mutable bool computed_edge_normals_{false}; |
| 187 |
|
| 188 |
mutable std::vector<PointXYZ> edge_normals_; |
| 189 |
|
| 190 |
static bool fpe_; |
| 191 |
}; |
| 192 |
|
| 193 |
//------------------------------------------------------------------------------------------------------ |
| 194 |
|
| 195 |
} // namespace util |
| 196 |
} // namespace atlas |