Debian Codegraph @

src/atlas/grid/detail/partitioner/MatchingMeshPartitionerBruteForce.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 "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