Submitted as: methods for assessment of models 22 Dec 2021
Submitted as: methods for assessment of models  22 Dec 2021
TriCCo v1.0.0 – a cubulationbased method for computing connected components on triangular grids
 ^{1}Department of Meteorology and Geophysics, University of Vienna, Austria
 ^{2}Institute for Algebra and Geometry, Department of Mathematics, OttovonGuericke University, Magdeburg, Germany
 ^{3}Institute of Meteorology and Climate Research  Department Troposphere Research Karlsruhe Institute of Technology, Germany
 ^{1}Department of Meteorology and Geophysics, University of Vienna, Austria
 ^{2}Institute for Algebra and Geometry, Department of Mathematics, OttovonGuericke University, Magdeburg, Germany
 ^{3}Institute of Meteorology and Climate Research  Department Troposphere Research Karlsruhe Institute of Technology, Germany
Abstract. We present a new method to identify connected components on a triangular grid. Triangular grids are, for example, used in atmosphere and climate models to discretize the horizontal dimension. Because they are unstructured, neighbor relations are not selfevident and identifying connected components is challenging. Our method addresses this challenge by involving the mathematical tool of cubulation. We show that cubulation allows one to map the 2d cells of the triangular grid onto the vertices of the 3d cells of a cubic grid. The latter is structured and so connected components can be readily identified on the cubic grid by previously developed software packages. An advantage is that the cubulation, i.e., the mapping between the triangular and cubic grids, needs to be computed only once, which should be benifical for analysing many data fields for the same grid.We further implement our method in a python package that we name TriCCo and that is made available via pypi and gitlab. We document the package, demonstrate its application using cloud data from the ICON atmosphere model, and characterize its computational performance. This shows that TriCCo is ready for triangular grids with 100,000 cells, but that its speed and memory requirements need to be improved to analyse larger grids.
Aiko Voigt et al.
Status: open (until 16 Feb 2022)

RC1: 'Comment on gmd2021349', Anonymous Referee #1, 23 Dec 2021
reply
General comments:
This is a wellwritten manuscript with beautiful figures. I enjoyed reading it
and learning about cubulation.One major issue puzzles me. I apologize if I've just missed something obvious.
The content of this review focuses on this issue. If I've missed something
obvious, simply explain and that will be sufficient. If my point is substantial,
then I'd like the revised manuscript to state clearly at the outset that
alternative, much more efficient, methods exist to solve the problem of finding
connected components of a triangulation.Again, the text itself is well written, and even if I'm right that the
particular problem of finding connected components is much more efficiently done
using standard graphtheoretic means, I suggest the text be published to
document this cubulation procedure in case it is of use in other contexts.Specific comments:
1. According to Table 2, the most expensive part of the workflow by a large
factor is the cubulation: hours vs seconds or minutes for the other steps. Given
this cost, why is it better to cubulate the triangulation and then run a
connectedcomponents algorithm on the cubulation than simply to compute the
connected components of the triangulation directly, using any of a number of
standard approaches?A standard approach is something like this, with details dependent on setting.
Represent the triangulation by
* vertex positions: an nvertex x ndim matrix P and
* triangles: an ntriangle x 3 matrix T of indices into P.
From this representation, one can construct a triangletriangle adjacency matrix
G = (V,E) in time linear in the number of objects, with edges E determined by an
adjacency rule, e.g. edge or vertex adjacency. (In the edgerule case, the
resulting graph is the dual graph defined in Defn. 2.1.) I want to emphasize
that because this procedure has linear time, computing adjacency data from the
raw triangulation is extremely fast, likely about as fast as the fastest entries
in Table 2.Now consider the cloud segmentation task. Each node v in V corresponds to a
triangle. In the cloud segmentation task, remove v and its edges from G if the
cloud fraction is below the threshold. One can then use a standard algorithm,
such as breadthfirst search, to find components in the resulting pruned graph.
Each of these operations is again linear in the number of objects. Thus, here
again this operation would be about as fast as the fastest entries in Table 2.
See, e.g., https://en.wikipedia.org/wiki/Component_(graph_theory).It is not clear to me what the computational complexity of your cubulation
implementation is, nor what the optimal complexity is. But for the former, we
can estimate from Table 2 as follows. The cost factor increase when going from
20km to 10km (4x more triangles) is 180min/12min = 15, just short of the 4^2 =
16 that would imply quadratic increase in cost. On the other hand, the factor is
9.6 when going from 40km to 20km: still superlinear (i.e., > 4) but less than
quadratic. It's possible a constant cost dominates at lower resolution, and the
15x in the 20>10 jump shows that an asymptotic quadratic cost is eventually
exposed.In any case, it is clear that cubulation is expensive.
Thus, I pose to you this question: Why should we prefer cubulation followed by
computing components rather than computing the components directly from the
triangletriangle adjacency graph?2. As a smaller issue, the figures and text imply the triangulation needs to be
geometrically regular so that the index scheme works. Is this a true constraint?
That is, will this method not work for geometrically unstructured triangular
grids? The graphbased method described above does not require regular
triangulations, nor for that matter a fixed type of polygon.Typos and grammar:
50: "we first introduce...and [to] rigorously define"
Fig. 2: "in [+the] same colors"
300: "their cube coordinates differ[s]"
Aiko Voigt et al.
Model code and software
TriCCo v1.0.0 python package Aiko Voigt, Petra Schwer, Noam von Rotberg, Nicole Knopf https://gitlab.phaidra.org/climate/tricco
Aiko Voigt et al.
Viewed
HTML  XML  Total  BibTeX  EndNote  

377  48  9  434  2  1 
 HTML: 377
 PDF: 48
 XML: 9
 Total: 434
 BibTeX: 2
 EndNote: 1
Viewed (geographical distribution)
Country  #  Views  % 

Total:  0 
HTML:  0 
PDF:  0 
XML:  0 
 1