| 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 |