1 /*
2 This file is part of CDO. CDO is a collection of Operators to manipulate and analyse Climate model Data.
3
4 Author: Asela Rajapakse
5 Uwe Schulzweida
6
7 */
8
9 /*
10 This module contains the following operators:
11 */
12
13 #include <cdi.h>
14
15 #include <utility>
16
17 #include "cdo_options.h"
18 #include "process_int.h"
19 #include <mpim_grid.h>
20 #include "gridreference.h"
21 #include "verifygrid.h"
22
23 static constexpr double eps = 0.000000001;
24
25 static void
printIndex2D(const size_t cell_no,const size_t nx)26 printIndex2D(const size_t cell_no, const size_t nx)
27 {
28 const auto iy = cell_no / nx;
29 const auto ix = cell_no - iy * nx;
30 fprintf(stdout, " [i=%zu j=%zu]", ix + 1, iy + 1);
31 }
32
33 static void
quick_sort(double * array,size_t array_length)34 quick_sort(double *array, size_t array_length)
35 {
36 if (array_length < 2) return;
37 const auto p = array[array_length / 2];
38
39 size_t i, j;
40 for (i = 0, j = array_length - 1;; i++, j--)
41 {
42 while (array[i] < p) i++;
43 while (p < array[j]) j--;
44 if (i >= j) break;
45 std::swap(array[i], array[j]);
46 }
47 quick_sort(array, i);
48 quick_sort(array + i, array_length - i);
49 }
50
51 /* Quicksort is called with a pointer to the array of center points to be sorted and an integer indicating its length.
52 * It sorts the array by its longitude coordinates */
53 static void
quick_sort_by_lon(double * array,size_t array_length)54 quick_sort_by_lon(double *array, size_t array_length)
55 {
56 if (array_length < 4) return;
57
58 const auto p = ((array_length / 2) % 2) ? array[(array_length / 2) + 1] : array[array_length / 2];
59
60 size_t i, j;
61 for (i = 0, j = array_length - 2;; i += 2, j -= 2)
62 {
63 while (array[i] < p) i += 2;
64
65 while (p < array[j]) j -= 2;
66
67 if (i >= j) break;
68
69 std::swap(array[i], array[j]);
70 std::swap(array[i + 1], array[j + 1]);
71 }
72
73 quick_sort_by_lon(array, i);
74 quick_sort_by_lon(array + i, array_length - i);
75 }
76
77 // This uses quicksort to sort the latitude coordinates in a subarray of all coordinates.
78 static void
quick_sort_of_subarray_by_lat(double * array,size_t subarray_start,size_t subarray_end)79 quick_sort_of_subarray_by_lat(double *array, size_t subarray_start, size_t subarray_end)
80 {
81 const auto subarray_length = (subarray_end - subarray_start) / 2 + 1;
82 Varray<double> subarray(subarray_length);
83 size_t subarray_index = 0;
84
85 for (size_t index = subarray_start + 1; index <= subarray_end + 1; index += 2)
86 {
87 subarray[subarray_index] = array[index];
88 subarray_index += 1;
89 }
90
91 quick_sort(subarray.data(), subarray_length);
92
93 subarray_index = 0;
94
95 for (size_t index = subarray_start + 1; index <= subarray_end + 1; index += 2)
96 {
97 array[index] = subarray[subarray_index];
98 subarray_index += 1;
99 }
100 }
101
102 static double
determinant(const double (& matrix)[3][3])103 determinant(const double (&matrix)[3][3])
104 {
105 // Calculates the determinant for a 3 x 3 matrix.
106
107 return matrix[0][0] * matrix[1][1] * matrix[2][2] + matrix[0][1] * matrix[1][2] * matrix[2][0]
108 + matrix[0][2] * matrix[1][0] * matrix[2][1] - matrix[0][2] * matrix[1][1] * matrix[2][0]
109 - matrix[0][1] * matrix[1][0] * matrix[2][2] - matrix[0][0] * matrix[1][2] * matrix[2][1];
110 }
111
112 static void
find_unit_normal(const Point3D & a,const Point3D & b,const Point3D & c,Point3D & unit_normal)113 find_unit_normal(const Point3D &a, const Point3D &b, const Point3D &c, Point3D &unit_normal)
114 {
115 // Calculates the unit normal for a plane defined on three points a, b, c in Euclidean space.
116
117 const double matrix_for_x[3][3] = { { 1, a.Y, a.Z }, { 1, b.Y, b.Z }, { 1, c.Y, c.Z } };
118 const double matrix_for_y[3][3] = { { a.X, 1, a.Z }, { b.X, 1, b.Z }, { c.X, 1, c.Z } };
119 const double matrix_for_z[3][3] = { { a.X, a.Y, 1 }, { b.X, b.Y, 1 }, { c.X, c.Y, 1 } };
120
121 const auto x = determinant(matrix_for_x);
122 const auto y = determinant(matrix_for_y);
123 const auto z = determinant(matrix_for_z);
124
125 const auto magnitude = std::sqrt(x * x + y * y + z * z);
126
127 unit_normal.X = x / magnitude;
128 unit_normal.Y = y / magnitude;
129 unit_normal.Z = z / magnitude;
130 }
131
132 int
find_coordinate_to_ignore(const Varray<Point3D> & cell_corners_xyz)133 find_coordinate_to_ignore(const Varray<Point3D> &cell_corners_xyz)
134 {
135 // Takes the first three corners/vertices of the cell and calculates the unit normal via determinants.
136
137 const auto &pcorner_coordinates1 = cell_corners_xyz[0];
138 const auto &pcorner_coordinates2 = cell_corners_xyz[1];
139 const auto &pcorner_coordinates3 = cell_corners_xyz[2];
140
141 Point3D surface_normal_of_the_cell;
142 find_unit_normal(pcorner_coordinates1, pcorner_coordinates2, pcorner_coordinates3, surface_normal_of_the_cell);
143
144 // The surface normal is used to choose the coordinate to ignore.
145
146 const auto abs_x = std::fabs(surface_normal_of_the_cell.X);
147 const auto abs_y = std::fabs(surface_normal_of_the_cell.Y);
148 const auto abs_z = std::fabs(surface_normal_of_the_cell.Z);
149
150 int coordinate_to_ignore = 3;
151
152 if (abs_x > abs_y)
153 {
154 if (abs_x > abs_z) coordinate_to_ignore = 1;
155 }
156 else
157 {
158 if (abs_y > abs_z) coordinate_to_ignore = 2;
159 }
160
161 return coordinate_to_ignore;
162 }
163
164 static inline double
is_point_left_of_edge(const Point & point1,const Point & point2,const Point & point)165 is_point_left_of_edge(const Point &point1, const Point &point2, const Point &point)
166 {
167 /*
168 Computes whether a point is left of the line through point1 and point2.
169 This is part of the solution to the point in polygon problem.
170
171 Returns: 0 if the point is on the line through point1 and point2
172 > 0 if the point is left of the line
173 < 0 if the point is right of the line
174
175 This algorithm is by Dan Sunday (geomalgorithms.com) and is completely free for use and modification.
176 */
177
178 return ((point2.x - point1.x) * (point.y - point1.y) - (point.x - point1.x) * (point2.y - point1.y));
179 }
180
181 int
winding_numbers_algorithm(const Varray<Point> & cell_corners,int number_corners,const Point & point)182 winding_numbers_algorithm(const Varray<Point> &cell_corners, int number_corners, const Point &point)
183 {
184 /*
185 Computes whether a point is inside the bounds of a cell. This is the solution to the point in polygon problem.
186 Returns 0 if the point is outside, returns 1 if the point is inside the cell. Based on an algorithm by Dan Sunday
187 (geomalgorithms.com). His algorithm is completely free for use and modification.
188 */
189
190 int winding_number = 0;
191
192 for (int k = 0; k < number_corners - 1; k++)
193 {
194 if (cell_corners[k].y <= point.y)
195 {
196 if (cell_corners[k + 1].y > point.y)
197 {
198 if (is_point_left_of_edge(cell_corners[k], cell_corners[k + 1], point) > 0) winding_number++;
199 }
200 }
201 else
202 {
203 if (cell_corners[k + 1].y <= point.y)
204 {
205 if (is_point_left_of_edge(cell_corners[k], cell_corners[k + 1], point) < 0) winding_number--;
206 }
207 }
208 }
209
210 return winding_number;
211 }
212
213 static double
sign(double x)214 sign(double x)
215 {
216 // Is +1 if x is positive, -1 if x is negative and 0 if x is zero.
217
218 return (x > 0.0) - (x < 0.0);
219 }
220
221 static bool
is_simple_polygon_convex(const Varray<Point> & cell_corners,int number_corners)222 is_simple_polygon_convex(const Varray<Point> &cell_corners, int number_corners)
223 {
224 // Tests in which direction the polygon winds when walking along its edges. Does so for all edges of the polygon.
225
226 double direction = 0.0;
227
228 for (int i = 0; i < number_corners - 2; i++)
229 {
230 auto turns_to = (cell_corners[i].x - cell_corners[i + 1].x) * (cell_corners[i + 1].y - cell_corners[i + 2].y)
231 - (cell_corners[i].y - cell_corners[i + 1].y) * (cell_corners[i + 1].x - cell_corners[i + 2].x);
232
233 // In the first iteration the direction of winding of the entire polygon is set. Better not be 0.
234
235 if (i == 1) direction = turns_to;
236
237 if (IS_NOT_EQUAL(sign(direction), sign(turns_to)))
238 {
239 if (IS_NOT_EQUAL(direction, 0.0)) return false;
240 }
241 else
242 {
243 direction = turns_to;
244 }
245 }
246
247 return true;
248 }
249
250 double
calculate_the_polygon_area(const Varray<Point> & cell_corners,int number_corners)251 calculate_the_polygon_area(const Varray<Point> &cell_corners, int number_corners)
252 {
253 /* This algorithm is based on the calculation from Wolfram Mathworld Polygon Area. It results in the area of planar
254 * non-self-intersecting polygon. */
255
256 double twice_the_polygon_area = 0.0;
257
258 for (int i = 0; i < number_corners - 1; i++)
259 twice_the_polygon_area += (cell_corners[i].x * cell_corners[i + 1].y) - (cell_corners[i + 1].x * cell_corners[i].y);
260
261 return twice_the_polygon_area / 2.0;
262 }
263
264 bool
are_polygon_vertices_arranged_in_clockwise_order(double cell_area)265 are_polygon_vertices_arranged_in_clockwise_order(double cell_area)
266 {
267 /* A negative area indicates a clockwise arrangement of vertices, a positive area a counterclockwise arrangement.
268 * There should be an area to begin with.
269 */
270 return cell_area < 0.0;
271 }
272
273 static void
create_sorted_point_array(size_t gridsize,const Varray<double> & grid_center_lon,const Varray<double> & grid_center_lat,Varray<double> & center_point_array)274 create_sorted_point_array(size_t gridsize, const Varray<double> &grid_center_lon, const Varray<double> &grid_center_lat,
275 Varray<double> ¢er_point_array)
276 {
277 for (size_t cell_no = 0; cell_no < gridsize; cell_no++)
278 {
279 center_point_array[cell_no * 2 + 0] = grid_center_lon[cell_no];
280 center_point_array[cell_no * 2 + 1] = grid_center_lat[cell_no];
281 }
282
283 // The cell center points are sorted by their first coordinate (lon) with quicksort.
284
285 quick_sort_by_lon(center_point_array.data(), gridsize * 2);
286
287 // Now the lat coordinates in subarrays that reflect equal lon coordinates are sorted with quicksort.
288
289 int subarray_start = 0;
290 int subarray_end = 0;
291
292 for (size_t cell_no = 0; cell_no < gridsize - 1; cell_no++)
293 {
294 if (cell_no == gridsize - 2)
295 {
296 subarray_end = gridsize * 2 - 2;
297 quick_sort_of_subarray_by_lat(center_point_array.data(), subarray_start, subarray_end);
298 }
299
300 if (std::fabs(center_point_array[cell_no * 2 + 0] - center_point_array[(cell_no + 1) * 2 + 0]) > eps)
301 {
302 subarray_end = cell_no * 2;
303 if ((subarray_end - subarray_start) > 1)
304 quick_sort_of_subarray_by_lat(center_point_array.data(), subarray_start, subarray_end);
305
306 subarray_start = subarray_end + 2;
307 }
308 }
309 }
310
311 static void
print_header(int gridtype,size_t gridsize,size_t nx,int gridno,int ngrids)312 print_header(int gridtype, size_t gridsize, size_t nx, int gridno, int ngrids)
313 {
314 if (ngrids == 1)
315 {
316 if (nx)
317 cdo_print(Blue("Grid consists of %zu (%zux%zu) cells (type: %s), of which"), gridsize, nx, gridsize / nx,
318 gridNamePtr(gridtype));
319 else
320 cdo_print(Blue("Grid consists of %zu cells (type: %s), of which"), gridsize, gridNamePtr(gridtype));
321 }
322 else
323 {
324 if (nx)
325 cdo_print(Blue("Grid no %u (of %u) consists of %zu (%zux%zu) cells (type: %s), of which"), gridno + 1, ngrids, gridsize, nx,
326 gridsize / nx, gridNamePtr(gridtype));
327 else
328 cdo_print(Blue("Grid no %u (of %u) consists of %zu cells (type: %s), of which"), gridno + 1, ngrids, gridsize,
329 gridNamePtr(gridtype));
330 }
331 }
332
333 static size_t
get_no_unique_center_points(size_t gridsize,size_t nx,const Varray<double> & grid_center_lon,const Varray<double> & grid_center_lat)334 get_no_unique_center_points(size_t gridsize, size_t nx, const Varray<double> &grid_center_lon,
335 const Varray<double> &grid_center_lat)
336 {
337 (void)nx;
338 // For performing the first test, an array of all center point coordinates is built.
339 Varray<double> center_points(gridsize * 2);
340 create_sorted_point_array(gridsize, grid_center_lon, grid_center_lat, center_points);
341
342 size_t no_unique_center_points = 1;
343 for (size_t cell_no = 0; cell_no < gridsize - 1; cell_no++)
344 {
345 if (std::fabs(center_points[cell_no * 2 + 0] - center_points[(cell_no + 1) * 2 + 0]) < eps
346 && std::fabs(center_points[cell_no * 2 + 1] - center_points[(cell_no + 1) * 2 + 1]) < eps)
347 {
348 if (Options::cdoVerbose)
349 {
350 fprintf(stdout, "Duplicate point [lon=%.5g lat=%.5g] was found", center_points[cell_no * 2 + 0],
351 center_points[cell_no * 2 + 1]);
352 /*
353 fprintf(stdout, "Duplicate point [lon=%.5g lat=%.5g] was found in cell no %zu",
354 center_points[cell_no * 2 + 0], center_points[cell_no * 2 + 1], cell_no + 1);
355 if (nx) printIndex2D(cell_no, nx);
356 */
357 fprintf(stdout, "\n");
358 }
359 }
360 else
361 {
362 no_unique_center_points++;
363 }
364 }
365
366 return no_unique_center_points;
367 }
368
369 void
set_cell_corners_xyz(int ncorner,const double * cell_corners_lon,const double * cell_corners_lat,Varray<Point3D> & cell_corners_xyz)370 set_cell_corners_xyz(int ncorner, const double *cell_corners_lon, const double *cell_corners_lat, Varray<Point3D> &cell_corners_xyz)
371 {
372 double corner_coordinates[3];
373 for (int k = 0; k < ncorner; k++)
374 {
375 // Conversion of corner spherical coordinates to Cartesian coordinates.
376 gcLLtoXYZ(cell_corners_lon[k], cell_corners_lat[k], corner_coordinates);
377
378 // The components of the result vector are appended to the list of cell corner coordinates.
379 cell_corners_xyz[k].X = corner_coordinates[0];
380 cell_corners_xyz[k].Y = corner_coordinates[1];
381 cell_corners_xyz[k].Z = corner_coordinates[2];
382 }
383 }
384
385 void
set_center_point_plane_projection(int coordinate_to_ignore,const Point3D & center_point_xyz,Point & center_point_plane_projection)386 set_center_point_plane_projection(int coordinate_to_ignore, const Point3D ¢er_point_xyz, Point ¢er_point_plane_projection)
387 {
388 // clang-format off
389 switch (coordinate_to_ignore)
390 {
391 case 1: center_point_plane_projection = Point {center_point_xyz.Y, center_point_xyz.Z}; break;
392 case 2: center_point_plane_projection = Point {center_point_xyz.Z, center_point_xyz.X}; break;
393 case 3: center_point_plane_projection = Point {center_point_xyz.X, center_point_xyz.Y}; break;
394 }
395 // clang-format on
396 }
397
398 void
set_cell_corners_plane_projection(int coordinate_to_ignore,int ncorner,const Varray<Point3D> & cell_corners_xyz,Varray<Point> & cell_corners_plane)399 set_cell_corners_plane_projection(int coordinate_to_ignore, int ncorner, const Varray<Point3D> &cell_corners_xyz,
400 Varray<Point> &cell_corners_plane)
401 {
402 switch (coordinate_to_ignore)
403 {
404 case 1:
405 for (int k = 0; k <= ncorner; k++) cell_corners_plane[k] = Point{ cell_corners_xyz[k].Y, cell_corners_xyz[k].Z };
406 break;
407 case 2:
408 for (int k = 0; k <= ncorner; k++) cell_corners_plane[k] = Point{ cell_corners_xyz[k].Z, cell_corners_xyz[k].X };
409 break;
410 case 3:
411 for (int k = 0; k <= ncorner; k++) cell_corners_plane[k] = Point{ cell_corners_xyz[k].X, cell_corners_xyz[k].Y };
412 break;
413 }
414 }
415
416 int
get_actual_number_of_corners(int ncorner,const Varray<Point3D> & cell_corners_xyz_open_cell)417 get_actual_number_of_corners(int ncorner, const Varray<Point3D> &cell_corners_xyz_open_cell)
418 {
419 auto actual_number_of_corners = ncorner;
420
421 for (int k = ncorner - 1; k > 0; k--)
422 {
423 if (IS_EQUAL(cell_corners_xyz_open_cell[k].X, cell_corners_xyz_open_cell[k - 1].X)
424 && IS_EQUAL(cell_corners_xyz_open_cell[k].Y, cell_corners_xyz_open_cell[k - 1].Y)
425 && IS_EQUAL(cell_corners_xyz_open_cell[k].Z, cell_corners_xyz_open_cell[k - 1].Z))
426 actual_number_of_corners--;
427 else
428 break;
429 }
430
431 return actual_number_of_corners;
432 }
433
434 int
get_no_duplicates(int actual_number_of_corners,const Varray<Point3D> & cell_corners_xyz_open_cell,std::vector<bool> & marked_duplicate_indices)435 get_no_duplicates(int actual_number_of_corners, const Varray<Point3D> &cell_corners_xyz_open_cell,
436 std::vector<bool> &marked_duplicate_indices)
437 {
438 for (int i = 0; i < actual_number_of_corners; i++) marked_duplicate_indices[i] = false;
439
440 int no_duplicates = 0;
441
442 for (int i = 0; i < actual_number_of_corners; i++)
443 for (int j = i + 1; j < actual_number_of_corners; j++)
444 if (std::fabs(cell_corners_xyz_open_cell[i].X - cell_corners_xyz_open_cell[j].X) < eps
445 && std::fabs(cell_corners_xyz_open_cell[i].Y - cell_corners_xyz_open_cell[j].Y) < eps
446 && std::fabs(cell_corners_xyz_open_cell[i].Z - cell_corners_xyz_open_cell[j].Z) < eps)
447 {
448 no_duplicates++;
449 marked_duplicate_indices[j] = true;
450 }
451
452 return no_duplicates;
453 }
454
455 void
copy_unique_corners(int actual_number_of_corners,const Varray<Point3D> & cell_corners_xyz_open_cell,const std::vector<bool> & marked_duplicate_indices,Varray<Point3D> & cell_corners_xyz_without_duplicates)456 copy_unique_corners(int actual_number_of_corners, const Varray<Point3D> &cell_corners_xyz_open_cell,
457 const std::vector<bool> &marked_duplicate_indices, Varray<Point3D> &cell_corners_xyz_without_duplicates)
458 {
459 int unique_corner_number = 0;
460
461 for (int k = 0; k < actual_number_of_corners; k++)
462 {
463 if (marked_duplicate_indices[k] == false)
464 {
465 cell_corners_xyz_without_duplicates[unique_corner_number] = cell_corners_xyz_open_cell[k];
466 unique_corner_number++;
467 }
468 }
469 }
470
471 static void
verify_grid(size_t gridsize,size_t nx,int ncorner,const Varray<double> & grid_center_lon,const Varray<double> & grid_center_lat,const Varray<double> & grid_corner_lon,const Varray<double> & grid_corner_lat)472 verify_grid(size_t gridsize, size_t nx, int ncorner, const Varray<double> &grid_center_lon, const Varray<double> &grid_center_lat,
473 const Varray<double> &grid_corner_lon, const Varray<double> &grid_corner_lat)
474 {
475 /*
476 First, this function performs the following test:
477
478 1) it tests whether there are duplicate cells in the given grid by comparing their center point
479
480 Additionally, on each cell of a given grid:
481
482 2) it tests whether all cells are convex and all cell bounds have the same orientation,
483 i.e. the corners of the cell are in clockwise or counterclockwise order
484
485 3) it tests whether the center point is within the bounds of the cell
486
487 The results of the tests are printed on stdout.
488 */
489 Point3D center_point_xyz;
490 Varray<Point3D> cell_corners_xyz_open_cell(ncorner);
491
492 Point center_point_plane_projection;
493
494 size_t no_of_cells_with_duplicates = 0;
495 size_t no_usable_cells = 0;
496 size_t no_convex_cells = 0;
497 size_t no_clockwise_cells = 0;
498 size_t no_counterclockwise_cells = 0;
499 size_t no_of_cells_with_center_points_out_of_bounds = 0;
500
501 std::vector<int> no_cells_with_a_specific_no_of_corners(ncorner, 0);
502
503 // Checking for the number of unique center point coordinates.
504 const auto no_unique_center_points = get_no_unique_center_points(gridsize, nx, grid_center_lon, grid_center_lat);
505
506 // used only actual_number_of_corners
507 std::vector<bool> marked_duplicate_indices(ncorner);
508 Varray<Point3D> cell_corners_xyz(ncorner + 1);
509 Varray<Point> cell_corners_plane_projection(ncorner + 1);
510 Varray<size_t> cells_with_duplicates;
511 cells_with_duplicates.reserve(gridsize);
512
513 /*
514 Latitude and longitude are spherical coordinates on a unit circle. Each such coordinate tuple is transformed into a
515 triple of Cartesian coordinates in Euclidean space. This is first done for the presumed center point of the cell
516 and then for all the corners of the cell.
517 */
518
519 for (size_t cell_no = 0; cell_no < gridsize; cell_no++)
520 {
521 // Conversion of center point spherical coordinates to Cartesian coordinates.
522 double center_coordinates[3];
523 gcLLtoXYZdeg(grid_center_lon[cell_no], grid_center_lat[cell_no], center_coordinates);
524 center_point_xyz.X = center_coordinates[0];
525 center_point_xyz.Y = center_coordinates[1];
526 center_point_xyz.Z = center_coordinates[2];
527
528 double corner_coordinates[3];
529 for (int k = 0; k < ncorner; k++)
530 {
531 // Conversion of corner spherical coordinates to Cartesian coordinates.
532 gcLLtoXYZdeg(grid_corner_lon[cell_no * ncorner + k], grid_corner_lat[cell_no * ncorner + k], corner_coordinates);
533
534 // The components of the result vector are appended to the list of cell corner coordinates.
535 cell_corners_xyz_open_cell[k].X = corner_coordinates[0];
536 cell_corners_xyz_open_cell[k].Y = corner_coordinates[1];
537 cell_corners_xyz_open_cell[k].Z = corner_coordinates[2];
538 }
539
540 /*
541 Not all cells have the same number of corners. The array, however, has ncorner * 3 values for each cell, where
542 ncorner is the maximum number of corners. Unused values have been filled with the values of the final cell. The
543 following identifies the surplus corners and gives the correct length of the cell.
544 */
545
546 auto actual_number_of_corners = get_actual_number_of_corners(ncorner, cell_corners_xyz_open_cell);
547
548 no_cells_with_a_specific_no_of_corners[actual_number_of_corners - 1] += 1;
549
550 // If there are less than three corners in the cell, it is unusable and considered degenerate. No area can be computed.
551
552 if (actual_number_of_corners < 3)
553 {
554 if (Options::cdoVerbose)
555 {
556 fprintf(stdout, "Less than three vertices found in cell no %zu", cell_no + 1);
557 if (nx) printIndex2D(cell_no, nx);
558 fprintf(stdout, ", omitted!");
559 fprintf(stdout, "\n");
560 }
561 continue;
562 }
563
564 no_usable_cells++;
565
566 // Checks if there are any duplicate vertices in the list of corners. Note that the last (additional) corner has not been set
567 // yet.
568
569 auto no_duplicates = get_no_duplicates(actual_number_of_corners, cell_corners_xyz_open_cell, marked_duplicate_indices);
570
571 if (Options::cdoVerbose)
572 {
573 for (int i = 0; i < actual_number_of_corners; i++)
574 {
575 if (marked_duplicate_indices[i])
576 {
577 fprintf(stdout, "Duplicate vertex [lon=%.5g lat=%.5g] was found in cell no %zu",
578 grid_corner_lon[cell_no * ncorner + i], grid_corner_lat[cell_no * ncorner + i], cell_no + 1);
579 if (nx) printIndex2D(cell_no, nx);
580 fprintf(stdout, "\n");
581 }
582 }
583 }
584
585 // Writes the unique corner vertices in a new array.
586
587 copy_unique_corners(actual_number_of_corners, cell_corners_xyz_open_cell, marked_duplicate_indices, cell_corners_xyz);
588
589 actual_number_of_corners -= no_duplicates;
590
591 // We are creating a closed polygon/cell by setting the additional last corner to be the same as the first one.
592
593 cell_corners_xyz[actual_number_of_corners] = cell_corners_xyz[0];
594
595 if (no_duplicates != 0)
596 {
597 no_of_cells_with_duplicates += 1;
598 cells_with_duplicates.push_back(cell_no);
599 }
600
601 /* If there are less than three corners in the cell left after removing duplicates, it is unusable and considered
602 * degenerate. No area can be computed. */
603
604 if (actual_number_of_corners < 3)
605 {
606 if (Options::cdoVerbose)
607 fprintf(stdout,
608 "Less than three vertices found in cell no %zu. This cell is considered degenerate and "
609 "will be omitted from further computation!\n",
610 cell_no + 1);
611
612 continue;
613 }
614
615 const auto coordinate_to_ignore = find_coordinate_to_ignore(cell_corners_xyz);
616
617 /* The remaining two-dimensional coordinates are extracted into one array for all the cell's corners and into one
618 * array for the center point. */
619
620 /* The following projection on the plane that two coordinate axes lie on changes the arrangement of the polygon
621 vertices if the coordinate to be ignored along the third axis is smaller than 0. In this case, the result of
622 the computation of the orientation of vertices needs to be inverted. Clockwise becomes counterclockwise and
623 vice versa. */
624
625 bool invert_result = false;
626 const auto cval = (coordinate_to_ignore == 1) ? cell_corners_xyz[0].X
627 : ((coordinate_to_ignore == 2) ? cell_corners_xyz[0].Y : cell_corners_xyz[0].Z);
628 if (cval < 0.0) invert_result = true;
629
630 set_center_point_plane_projection(coordinate_to_ignore, center_point_xyz, center_point_plane_projection);
631 set_cell_corners_plane_projection(coordinate_to_ignore, actual_number_of_corners, cell_corners_xyz,
632 cell_corners_plane_projection);
633
634 // Checking for convexity of the cell.
635
636 if (is_simple_polygon_convex(cell_corners_plane_projection, actual_number_of_corners + 1))
637 {
638 no_convex_cells += 1;
639 }
640 else if (Options::cdoVerbose)
641 {
642 fprintf(stdout, "Vertices are not convex in cell no %zu", cell_no + 1);
643 if (nx) printIndex2D(cell_no, nx);
644 fprintf(stdout, "\n");
645 }
646
647 // Checking the arrangement or direction of cell vertices.
648
649 const auto polygon_area = calculate_the_polygon_area(cell_corners_plane_projection, actual_number_of_corners + 1);
650 auto is_clockwise = are_polygon_vertices_arranged_in_clockwise_order(polygon_area);
651
652 /* If the direction of the vertices was flipped during the projection onto the two-dimensional plane, the previous
653 * result needs to be inverted now. */
654
655 if (invert_result) is_clockwise = !is_clockwise;
656
657 // The overall counter of (counter)clockwise cells is increased by one.
658 if (is_clockwise)
659 {
660 no_clockwise_cells += 1;
661 if (Options::cdoVerbose)
662 {
663 fprintf(stdout, "Vertices arranged in a clockwise order in cell no %zu", cell_no + 1);
664 if (nx) printIndex2D(cell_no, nx);
665 fprintf(stdout, "\n");
666 }
667 }
668 else
669 {
670 no_counterclockwise_cells += 1;
671 }
672
673 // The winding numbers algorithm is used to test whether the presumed center point is within the bounds of the cell.
674 auto winding_number
675 = winding_numbers_algorithm(cell_corners_plane_projection, actual_number_of_corners + 1, center_point_plane_projection);
676
677 // if ( winding_number == 0 ) printf("%d,", cell_no+1);
678 if (winding_number == 0) no_of_cells_with_center_points_out_of_bounds += 1;
679
680 if (Options::cdoVerbose && winding_number == 0)
681 {
682 fprintf(stdout, "Center point [lon=%.5g lat=%.5g] outside bounds [", grid_center_lon[cell_no], grid_center_lat[cell_no]);
683 for (int k = 0; k < ncorner; k++)
684 fprintf(stdout, " %.5g/%.5g", grid_corner_lon[cell_no * ncorner + k], grid_corner_lat[cell_no * ncorner + k]);
685 fprintf(stdout, "] in cell no %zu", cell_no + 1);
686 if (nx) printIndex2D(cell_no, nx);
687 fprintf(stdout, "\n");
688 }
689 }
690
691 const auto no_nonunique_cells = gridsize - no_unique_center_points;
692 const auto no_nonconvex_cells = gridsize - no_convex_cells;
693 const auto no_nonusable_cells = gridsize - no_usable_cells;
694
695 for (int i = 2; i < ncorner; i++)
696 if (no_cells_with_a_specific_no_of_corners[i])
697 cdo_print(Blue("%9d cells have %d vertices"), no_cells_with_a_specific_no_of_corners[i], i + 1);
698
699 if (no_of_cells_with_duplicates) cdo_print(Blue("%9zu cells have duplicate vertices"), no_of_cells_with_duplicates);
700
701 if (no_nonusable_cells) cdo_print(Red("%9zu cells have unusable vertices"), no_nonusable_cells);
702
703 if (no_nonunique_cells) cdo_print(Red("%9zu cells are not unique"), no_nonunique_cells);
704
705 if (no_nonconvex_cells) cdo_print(Red("%9zu cells are non-convex"), no_nonconvex_cells);
706
707 if (no_clockwise_cells) cdo_print(Red("%9zu cells have their vertices arranged in a clockwise order"), no_clockwise_cells);
708
709 if (no_of_cells_with_center_points_out_of_bounds)
710 cdo_print(Red("%9zu cells have their center point located outside their boundaries"),
711 no_of_cells_with_center_points_out_of_bounds);
712
713 // cdo_print("");
714 }
715
716 static void
print_lonlat(int dig,int gridID,size_t gridsize,const Varray<double> & lon,const Varray<double> & lat)717 print_lonlat(int dig, int gridID, size_t gridsize, const Varray<double> &lon, const Varray<double> &lat)
718 {
719 size_t num_lons_nan = 0;
720 for (size_t i = 0; i < gridsize; ++i)
721 if (std::isnan(lon[i])) num_lons_nan++;
722 if (num_lons_nan) cdo_print(Red("%9zu longitudes are NaN"), num_lons_nan);
723
724 size_t num_lats_nan = 0;
725 for (size_t i = 0; i < gridsize; ++i)
726 if (std::isnan(lat[i])) num_lats_nan++;
727 if (num_lats_nan) cdo_print(Red("%9zu latitudes are NaN"), num_lats_nan);
728
729 char name[CDI_MAX_NAME];
730 int length = CDI_MAX_NAME;
731 cdiInqKeyString(gridID, CDI_XAXIS, CDI_KEY_NAME, name, &length);
732 const auto xmm = varray_min_max(gridsize, lon);
733 cdo_print("%10s : %.*g to %.*g degrees", name, dig, xmm.min, dig, xmm.max);
734 if (xmm.min < -720.0 || xmm.max > 720.0) cdo_warning("Grid cell center longitudes out of range!");
735
736 length = CDI_MAX_NAME;
737 cdiInqKeyString(gridID, CDI_YAXIS, CDI_KEY_NAME, name, &length);
738 const auto ymm = varray_min_max(gridsize, lat);
739 cdo_print("%10s : %.*g to %.*g degrees", name, dig, ymm.min, dig, ymm.max);
740 if (ymm.min < -90.00001 || ymm.max > 90.00001) cdo_warning("Grid cell center latitudes out of range!");
741 }
742
743 void *
Verifygrid(void * argument)744 Verifygrid(void *argument)
745 {
746 cdo_initialize(argument);
747
748 cdo_operator_add("verifygrid", 0, 0, nullptr);
749
750 operator_check_argc(0);
751
752 const auto streamID = cdo_open_read(0);
753 const auto vlistID = cdo_stream_inq_vlist(streamID);
754
755 const auto ngrids = vlistNgrids(vlistID);
756 for (int gridno = 0; gridno < ngrids; ++gridno)
757 {
758 bool lgeo = true;
759
760 auto gridID = vlistGrid(vlistID, gridno);
761 const auto gridtype = gridInqType(gridID);
762
763 if (gridtype == GRID_GENERIC || gridtype == GRID_SPECTRAL) lgeo = false;
764
765 if (gridtype == GRID_GME) gridID = gridToUnstructured(gridID, 1);
766
767 if (lgeo && gridtype != GRID_UNSTRUCTURED && gridtype != GRID_CURVILINEAR) gridID = gridToCurvilinear(gridID, 1);
768
769 if (gridtype == GRID_UNSTRUCTURED && !gridHasCoordinates(gridID))
770 {
771 const auto reference = dereferenceGrid(gridID);
772 if (reference.isValid) gridID = reference.gridID;
773 if (reference.notFound)
774 {
775 cdo_print("Reference to source grid not found!");
776 lgeo = false;
777 }
778 }
779
780 const auto gridsize = gridInqSize(gridID);
781 auto nx = gridInqXsize(gridID);
782 auto ny = gridInqYsize(gridID);
783 nx = (nx * ny == gridsize) ? nx : 0;
784
785 if (lgeo)
786 {
787 const auto ncorner = (gridInqType(gridID) == GRID_UNSTRUCTURED) ? gridInqNvertex(gridID) : 4;
788
789 if (!gridHasCoordinates(gridID)) cdo_abort("Cell center coordinates missing!");
790
791 Varray<double> grid_center_lat(gridsize), grid_center_lon(gridsize);
792
793 gridInqYvals(gridID, grid_center_lat.data());
794 gridInqXvals(gridID, grid_center_lon.data());
795
796 // Convert lat/lon units if required
797 cdo_grid_to_degree(gridID, CDI_XAXIS, gridsize, grid_center_lon.data(), "grid center lon");
798 cdo_grid_to_degree(gridID, CDI_YAXIS, gridsize, grid_center_lat.data(), "grid center lat");
799
800 print_header(gridtype, gridsize, nx, gridno, ngrids);
801
802 if (gridHasBounds(gridID))
803 {
804 if (ncorner == 0) cdo_abort("Number of cell corners undefined!");
805 const auto nalloc = ncorner * gridsize;
806 Varray<double> grid_corner_lat(nalloc), grid_corner_lon(nalloc);
807
808 gridInqYbounds(gridID, grid_corner_lat.data());
809 gridInqXbounds(gridID, grid_corner_lon.data());
810
811 cdo_grid_to_degree(gridID, CDI_XAXIS, ncorner * gridsize, grid_corner_lon.data(), "grid corner lon");
812 cdo_grid_to_degree(gridID, CDI_YAXIS, ncorner * gridsize, grid_corner_lat.data(), "grid corner lat");
813
814 verify_grid(gridsize, nx, ncorner, grid_center_lon, grid_center_lat, grid_corner_lon, grid_corner_lat);
815 }
816 else
817 {
818 cdo_warning("Grid cell corner coordinates missing!");
819 }
820
821 const int dig = Options::CDO_flt_digits;
822 print_lonlat(dig, gridID, gridsize, grid_center_lon, grid_center_lat);
823 }
824 else
825 {
826 if (ngrids == 1)
827 cdo_print(Blue("Grid consists of %zu points (type: %s)"), gridsize, gridNamePtr(gridtype));
828 else
829 cdo_print(Blue("Grid no %u (of %u) consists of %zu points (type: %s)"), gridno + 1, ngrids, gridsize,
830 gridNamePtr(gridtype));
831 // cdo_print("");
832 }
833 }
834
835 cdo_stream_close(streamID);
836
837 cdo_finish();
838
839 return nullptr;
840 }
841