| 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 "atlas/grid/detail/partitioner/MatchingMeshPartitionerBruteForce.h" |
| 12 |
|
| 13 |
#include <vector> |
| 14 |
|
| 15 |
#include "eckit/log/ProgressTimer.h" |
| 16 |
|
| 17 |
#include "atlas/array/ArrayView.h" |
| 18 |
#include "atlas/field/Field.h" |
| 19 |
#include "atlas/grid.h" |
| 20 |
#include "atlas/mesh/Elements.h" |
| 21 |
#include "atlas/mesh/Mesh.h" |
| 22 |
#include "atlas/mesh/Nodes.h" |
| 23 |
#include "atlas/parallel/mpi/mpi.h" |
| 24 |
#include "atlas/runtime/Exception.h" |
| 25 |
#include "atlas/runtime/Log.h" |
| 26 |
#include "atlas/runtime/Trace.h" |
| 27 |
#include "atlas/util/CoordinateEnums.h" |
| 28 |
|
| 29 |
namespace atlas { |
| 30 |
namespace grid { |
| 31 |
namespace detail { |
| 32 |
namespace partitioner { |
| 33 |
|
| 34 |
namespace { |
| 35 |
|
| 36 |
PartitionerBuilder<MatchingMeshPartitionerBruteForce> __builder("brute-force"); |
| 37 |
|
| 38 |
double dot_sign(const double& Ax, const double& Ay, const double& Bx, const double& By, const double& Cx, |
| 39 |
const double& Cy) { |
| 40 |
return (Ax - Cx) * (By - Cy) - (Bx - Cx) * (Ay - Cy); |
| 41 |
} |
| 42 |
|
| 43 |
/// Point-in-triangle test |
| 44 |
/// @note "dot product" test, equivalent to half-plane check |
| 45 |
/// @see |
| 46 |
/// http://stackoverflow.com/questions/2049582/how-to-determine-if-a-point-is-in-a-2d-triangle |
| 47 |
bool point_in_triangle(const PointLonLat& P, const PointLonLat& A, const PointLonLat& B, const PointLonLat& C) { |
| 48 |
// Compute signs of dot products |
| 49 |
const bool b1 = dot_sign(P.lon(), P.lat(), A.lon(), A.lat(), B.lon(), B.lat()) < 0, |
| 50 |
b2 = dot_sign(P.lon(), P.lat(), B.lon(), B.lat(), C.lon(), C.lat()) < 0, |
| 51 |
b3 = dot_sign(P.lon(), P.lat(), C.lon(), C.lat(), A.lon(), A.lat()) < 0; |
| 52 |
|
| 53 |
// Check if point is in triangle |
| 54 |
// - check for b1 && b2 && b3 only works for triangles ordered |
| 55 |
// counter-clockwise |
| 56 |
// - check for b1==b2 && b2==b3 works for both, equivalent to "all points on |
| 57 |
// the same side" |
| 58 |
return (b1 == b2) && (b2 == b3); |
| 59 |
} |
| 60 |
|
| 61 |
/// Point-in-quadrilateral test |
| 62 |
/// @note limited to convex quadrilaterals, @see |
| 63 |
/// https://en.wikipedia.org/wiki/Convex_polygon |
| 64 |
bool point_in_quadrilateral(const PointLonLat& P, const PointLonLat& A, const PointLonLat& B, const PointLonLat& C, |
| 65 |
const PointLonLat& D) { |
| 66 |
const bool b1 = dot_sign(P.lon(), P.lat(), A.lon(), A.lat(), B.lon(), B.lat()) < 0, |
| 67 |
b2 = dot_sign(P.lon(), P.lat(), B.lon(), B.lat(), C.lon(), C.lat()) < 0, |
| 68 |
b3 = dot_sign(P.lon(), P.lat(), C.lon(), C.lat(), D.lon(), D.lat()) < 0, |
| 69 |
b4 = dot_sign(P.lon(), P.lat(), D.lon(), D.lat(), A.lon(), A.lat()) < 0; |
| 70 |
return (b1 == b2) && (b2 == b3) && (b3 == b4); |
| 71 |
} |
| 72 |
|
| 73 |
} // namespace |
| 74 |
|
| 75 |
void MatchingMeshPartitionerBruteForce::partition(const Grid& grid, int partitioning[]) const { |
| 76 |
ATLAS_TRACE("MatchingMeshPartitionerBruteForce::partition"); |
| 77 |
|
| 78 |
const auto& comm = mpi::comm(prePartitionedMesh_.mpi_comm()); |
| 79 |
const int mpi_rank = int(comm.rank()); |
| 80 |
|
| 81 |
// Point coordinates |
| 82 |
// - use a bounding box to quickly discard points, |
| 83 |
// - except when that is above/below bounding box but poles should be included |
| 84 |
// FIXME: THIS IS A HACK! the coordinates include North/South Pole |
| 85 |
// (first/last partitions only) |
| 86 |
|
| 87 |
ATLAS_ASSERT(grid.domain().global()); |
| 88 |
bool includesNorthPole = (mpi_rank == 0); |
| 89 |
bool includesSouthPole = (mpi_rank == (int(comm.size()) - 1)); |
| 90 |
|
| 91 |
ATLAS_ASSERT(prePartitionedMesh_.nodes().size()); |
| 92 |
auto lonlat_src = array::make_view<double, 2>(prePartitionedMesh_.nodes().lonlat()); |
| 93 |
|
| 94 |
std::vector<PointLonLat> coordinates; |
| 95 |
coordinates.reserve(lonlat_src.shape(0)); |
| 96 |
PointLonLat coordinatesMin = PointLonLat(lonlat_src(0, LON), lonlat_src(0, LAT)); |
| 97 |
PointLonLat coordinatesMax = coordinatesMin; |
| 98 |
|
| 99 |
for (idx_t i = 0; i < lonlat_src.shape(0); ++i) { |
| 100 |
PointLonLat A(lonlat_src(i, LON), lonlat_src(i, LAT)); |
| 101 |
coordinatesMin = PointLonLat::componentsMin(coordinatesMin, A); |
| 102 |
coordinatesMax = PointLonLat::componentsMax(coordinatesMax, A); |
| 103 |
coordinates.emplace_back(A); |
| 104 |
} |
| 105 |
|
| 106 |
{ |
| 107 |
eckit::ProgressTimer timer("Partitioning target", grid.size(), "point", double(10), atlas::Log::trace()); |
| 108 |
auto grid_iter = grid.lonlat().begin(); |
| 109 |
for (idx_t i = 0; i < grid.size(); ++i, ++grid_iter) { |
| 110 |
partitioning[i] = -1; |
| 111 |
const PointLonLat& P = *grid_iter; |
| 112 |
|
| 113 |
if (coordinatesMin[LON] <= P[LON] && P[LON] <= coordinatesMax[LON] && coordinatesMin[LAT] <= P[LAT] && |
| 114 |
P[LAT] <= coordinatesMax[LAT]) { |
| 115 |
const mesh::Cells& elements_src = prePartitionedMesh_.cells(); |
| 116 |
const idx_t nb_types = elements_src.nb_types(); |
| 117 |
bool found = false; |
| 118 |
|
| 119 |
for (idx_t t = 0; t < nb_types && !found; ++t) { |
| 120 |
idx_t idx[4]; |
| 121 |
const mesh::Elements& elements = elements_src.elements(t); |
| 122 |
const mesh::BlockConnectivity& conn = elements.node_connectivity(); |
| 123 |
|
| 124 |
const idx_t nb_nodes = elements.nb_nodes(); |
| 125 |
ATLAS_ASSERT((nb_nodes == 3 && elements.name() == "Triangle") || |
| 126 |
(nb_nodes == 4 && elements.name() == "Quadrilateral")); |
| 127 |
|
| 128 |
for (idx_t j = 0; j < elements.size() && !found; ++j) { |
| 129 |
idx[0] = conn(j, 0); |
| 130 |
idx[1] = conn(j, 1); |
| 131 |
idx[2] = conn(j, 2); |
| 132 |
idx[3] = nb_nodes > 3 ? conn(j, 3) : 0; |
| 133 |
|
| 134 |
if ((elements.name() == "Triangle" && |
| 135 |
point_in_triangle(P, coordinates[idx[0]], coordinates[idx[1]], coordinates[idx[2]])) || |
| 136 |
(elements.name() == "Quadrilateral" && |
| 137 |
point_in_quadrilateral(P, coordinates[idx[0]], coordinates[idx[1]], coordinates[idx[2]], |
| 138 |
coordinates[idx[3]]))) { |
| 139 |
partitioning[i] = mpi_rank; |
| 140 |
found = true; |
| 141 |
} |
| 142 |
} |
| 143 |
} |
| 144 |
} |
| 145 |
else if ((includesNorthPole && P[LAT] > coordinatesMax[LAT]) || |
| 146 |
(includesSouthPole && P[LAT] < coordinatesMin[LAT])) { |
| 147 |
partitioning[i] = mpi_rank; |
| 148 |
} |
| 149 |
} |
| 150 |
} |
| 151 |
|
| 152 |
// Synchronize the partitioning and return a grid partitioner |
| 153 |
comm.allReduceInPlace(partitioning, grid.size(), eckit::mpi::Operation::MAX); |
| 154 |
const int min = *std::min_element(partitioning, partitioning + grid.size()); |
| 155 |
if (min < 0) { |
| 156 |
throw_Exception( |
| 157 |
"Could not find partition for target node (source " |
| 158 |
"mesh does not contain all target grid points)", |
| 159 |
Here()); |
| 160 |
} |
| 161 |
} |
| 162 |
|
| 163 |
} // namespace partitioner |
| 164 |
} // namespace detail |
| 165 |
} // namespace grid |
| 166 |
} // namespace atlas |