POLYLLA: polygonal meshing algorithm based on terminal-edge regions

Abstract

This paper presents an algorithm to generate a new kind of polygonal mesh obtained from triangulations. Each polygon is built from a terminal-edge region surrounded by edges that are not the longest-edge of any of the two triangles that share them. The algorithm is termed Polylla and is divided into three phases. The first phase consists of labeling each edge of the input triangulation according to its size; the second phase builds polygons (simple or not) from terminal-edges regions using the label system; and the third phase transforms each non simple polygon into simple ones. The final mesh contains polygons with convex and non convex shape. Since Voronoi-based meshes are currently the most used polygonal meshes, we compare some geometric properties of our meshes against constrained Voronoi meshes. Several experiments were run to compare the shape and size of polygons, the number of final mesh points and polygons. For the same input, Polylla meshes contain less polygons than Voronoi meshes and the algorithm is simpler and faster than the algorithm to generate constrained Voronoi meshes. Finally, we have validated Polylla meshes by solving the Laplace equation on an L-shaped domain using the virtual element method (VEM). We show that the numerical performance of the VEM using Polylla meshes and Voronoi meshes is similar.

1 Introduction

Meshes composed of triangles and quadrilaterals are common in simulations using the finite element method (FEM). One of the main requirements is that polygons (elements) need to obey specific quality criteria such as angles not too large or small, or reasonable aspect ratio and area, among others. To fulfill these criteria, sometimes the insertion of a large number of points and elements is required in order to properly model a domain, increasing the time needed to make a simulation. New methods such as the virtual element method (VEM) [1, 2] can use any polygon as basic cell. Our main research interest is to explore how far the VEM can handle non-convex and convex polygons and still be able to compute accurate simulation results. Our goal is to build a new tool that allows the VEM community [3] to model and simulate more complex problems than before, both in 2D and 3D.

In this context, the VEM presents an opportunity to explore new kind of polygonal meshes and new algorithms to generate them. Our main research questions are: Can terminal-edge regions ¹ be adapted to be used as good basic cells for polygonal numerical methods such as the VEM? Do this kind of meshes require less polygons to model the same problem than polygonal meshes based on the Voronoi diagram? Our hypotheses are: (1) Terminal-edge regions can be transformed into simple polygons and used as basic cells, (2) the domain geometry can be fitted using less elements than constrained Voronoi meshes, (3) this kind of polygonal meshes can be used with the VEM.

In this paper, we propose an algorithm to generate meshes that adapt to a geometric domain specified through planar line straight graph (PLSG) using polygons of any shape, and respecting the point distribution given as input. The algorithm reads as input a triangulation and uses the concept of terminal-edge region as basis to build polygons. Terminal-edge regions can generate non-simple polygons, so we also propose an algorithm to divide them into simple ones. We run several experiments to show properties of these polygons and compare the generated meshes against constrained Voronoi meshes. Moreover, we validate the polygonal meshes over a classical problem to show that these meshes can be used to solve problems with the VEM. As an example, Fig. 1 shows a polygonal mesh generated with the algorithm proposed in this paper.

Fig. 1

Polygonal mesh of a Chilean moth (Polilla Venusta) composed of 513 polygons, 1351 vertices and 2455 edges. The original PLSG contains 616 points and segments. A conforming Delaunay triangulation with maximum edge size of 160 was generated using Pygalmesh [5]. The resulting triangulation contains 1351 vertices (the same of the output), 2083 triangles and 3432 edges

Any triangulation can be used as input but through this paper the polygonal meshes are generated from a Delaunay triangulation. It is known that Delaunay triangulations are the ones that maximize the smallest angle among all the triangulations of a point set. Since the proposed algorithm does not divide any input triangle, the smallest angle of the triangulation is a lower bound for the minimum interior angle of the polygonal mesh.

The main contributions of this paper are:

• A simple and automatic tool to generate polygonal meshes composed of convex or/and non-convex polygons, fitting exactly the input domain and respecting the initial point distribution.

• A new kind of polygonal meshes composed of less polygons and points than constrained Voronoi meshes for the same input.

• The algorithm benefits from robust tools such as Detri2d or Triangle to generate the initial constrained Delaunay triangulation in similar way some constrained Voronoi meshing algorithms do. Voronoi meshing algorithms require to compute new points (Voronoi points), cut non-bounded Voronoi regions to fit the domain and insert new points at the domain boundary to create the constrained Voronoi mesh. So the proposed algorithm is faster than the algorithm to generate constrained Voronoi meshes.

This paper is organized as follows: Sect. 2 presents and discusses the-state-of-art; Sect. 3 introduces the basic concepts that explains the algorithm; Sect. 4 describes the main steps of the proposed algorithm and the used data structure; in Sect. 5 we analyse some geometric features of the generated meshes and gives a comparison against the constrained Voronoi meshes; Sect. 6 shows a preliminary assessment of the meshes in the virtual element method (VEM) and Sect. 7 presents our conclusions and ongoing work.

2 Related work

Mesh generation refers to the methods used to discretize a geometric domain into smaller elements without overlap. Those methods has been widely studied due to their importance in science and engineering. Meshes are used in geographic information systems [6], computer vision [7], numerical methods [8], computer tomography [9], among other applications. Common methods used to generate unstructured polygon meshes are the Delaunay methods [10], Voronoi diagram methods [11,12,13], advancing front method [14, 15], quadtree based methods [16,17,18] and hybrids methods [19, 20], among others. In general, meshing algorithms can be classified into two groups [21, 22]: (1) direct algorithms: meshes are generated from the input geometry, and (2) indirect algorithms: meshes are generated starting from an input mesh, typically an initial triangle mesh. Indirect methods is a common approach to generate quadrilateral meshes by mixing triangles of an initial triangulation [23,24,25]. The advantage of using indirect methods is that currently triangular meshes are easy to generate because several robust open source and free tools [26,27,28,29] are available. Polylla mesh generation is an indirect method as it is based on mixing triangles from an initial triangulation.

In standard FEM, the most used 2D meshes are triangulations [26, 27, 30] and quadrilateral meshes [31,32,33]. 2D Mixed meshes composed of triangles and quadrilaterals have also been used, but are not so common as the previous ones [34]. Other numerical methods such as the Voronoi Cell Finite Element Method (VCFEM) [35] and Polygonal Finite Element method (PFEM) [36] use the constrained Voronoi diagram as the polygonal mesh, where the Voronoi cells are the mesh elements [37,38,39].

The generalization of finite element methods to include polygons as part of the mesh elements is not recent [40,41,42]. Polygonal elements are usually generated by using a quadtree approach and from Voronoi based algorithms. In particular, the vem was introduced in the last decade [1, 2] and since then, several research groups have been developing computational frameworks in order to explore new problems. To mention some applications, the vem has been formulated and applied to solve linear elastic and inelastic solid mechanics problems [43], in fluid mechanics [44, 45], in the optimization of a fluid problem through a discrete network [46], for compressible and incompressible finite deformations [47, 48] and brittle crack propagation [49].

VEM has a flexibility in dealing with complex cell shapes that can even be non convex and have an arbitrary number of vertices [50]. As an example, meshes composed of animal shape polygons were used for crack propagation to show that the vem can deal with non-convex element shapes [3]. Similar experiments using the vem in meshes composed of high irregular shapes are described in [51, 52].

To our knowledge, no algorithm for the automatic generation of 2D meshes formed by polygons (convex or not) has been published for the vem in arbitrary domains. We recently developed a tool to generate a particular kind of polygonal meshes in the context of modeling the rock packing problem inside a square container [53]. The rocks were modeled as convex polygons and the space with general polygons. We ran preliminary simulations using the vem and also experienced that the vem is very robust under irregular polygonal shapes [53].

3 Basic concepts

The proposed polygonal meshing algorithm is based on two concepts: Longest-edge propagation path (Lepp) introduced in [4] and terminal-edge regions defined in [54, 55]. We briefly review these concepts and some related properties in this section.

3.1 Terminal-edge regions

In any triangulation, triangles can be grouped under the Longest-edge propagation path concept defined as follows:

Definition 1

Longest-edge propagation path [4]: For any triangle $t_0$ in any triangulation $\Omega$, the Lepp($t_0$) is the ordered list of all the triangles $t_0$, $t_1$, $t_2$, ..., $t_{l-1}$, $t_{l}$, such that $t_{i}$ is the neighbor triangle of $t_{i-1}$ by the longest-edge of $t_{i-1}$, for $i = 1,2,\dots ,l$. The longest-edge shared by $t_{l-1}$ and $t_l$ is a terminal-edge and $t_{l-1}$ and $t_l$ are terminal-triangles. As an example, in Fig. 2a the Lepp($t_0$) is shown in blue, its terminal edge is shown in red and its terminal triangles labeled as $t_1$ and $t_2$.

Fig. 2

Terminal-edge region. a Longest-edge propagation of $t_0$ where the red edge is the terminal-edge. b Four Lepps: Lepp($t_a$), Lepp($t_b$), Lepp($t_c$) and Lepp($t_d$), with the same terminal-edge. c Terminal-edge region generated by the union of Lepp($t_a$), Lepp($t_b$), Lepp($t_c$) and Lepp($t_d$)

A triangle edge can be classified according to its length inside the two triangles that share it. Therefore, given an edge e and two triangles $t_1$, $t_2$ that share e, we can label e as:

• Terminal-edge [4]: e is the longest-edge of $t_1$ and $t_2$.

• Frontier-edge [54]: e is neither the longest-edge of $t_1$ nor $t_2$.

• Internal-edge: e is the longest edge of $t_1$ but not of $t_2$ or vice-versa.

• Boundary edge: e belongs to one triangle. In the proposed algorithm boundary edges are handled as frontier edges.

It is worth mentioning that edges of equal length can appear. Therefore, in case there are equilateral triangles, each edge is chosen arbitrarily as the longest-, the middle- and smallest-edge. When there are isosceles triangles, something similar is done for equal size edges.

Definition 2

Terminal-edge region [54]: A terminal-edge region R is a region formed by the union of all triangles $t_i$ such that Lepp($t_i$) has the same terminal-edge. In case the terminal-edge region is partially delimited by boundary edges the region will be called boundary terminal-edge region. Figure 2c shows the terminal-edge region formed by the union of Lepp($t_a$), Lepp($t_b$), Lepp($t_c$) and Lepp($t_d$).

We have already used the concept of terminal-edge region for finding polygonal voids (holes) inside a point set [54, 56] and proven some geometric properties. In order to facilitate understanding of the algorithm we are recalling the most important here:

• Terminal-edge regions are surrounded by frontier-edges [54].

• Terminal-edge regions cover the whole domain without overlapping [54, 55].

• Terminal-edge-regions might include frontier-edges in their interior. We have called this kind of frontier-edge a barrier-edge [54, 55].

Let us use Fig. 3 to illustrate an example of a partition generated by terminal-edge regions. Fig. 3a shows an input point set; Fig. 3b shows the Delaunay triangulation of this point set where terminal-edges are drawn using red dashed lines, internal-edges using black dashed lines and frontier-edges using solid lines. Fig. 3c shows the polygons defined by terminal-edge regions using a different color, where each polygon is delimited by frontier edges. It can be noticed that the green polygon is a non-simple polygon because it includes a barrier-edge. For simplicity, in the case e is a domain boundary edge, e will be considered a frontier-edge too (see the edges belonging to the square in Fig. 3b, c).

Fig. 3

a Initial random point set. b Delaunay triangulation: solid lines are frontier-edges, dashed black lines are internal-edges and red dashed lines are terminal-edges. c Polygon partition from terminal-edge regions

3.2 Terminal-edge regions as polygons

As we have said in the previous section, terminal-edge regions generate a polygon partition of the domain without overlapping. Depending on the point distribution, polygons can be simple or non-simple polygons. Non-simple polygons appear when terminal-edge regions include barrier-edges. As observed in Fig. 3, the domain was tessellated into 14 polygons where only the green region is represented by a non-simple polygon because it includes one barrier-edge.

To build a conforming polygon tessellation from the partition generated by the terminal-edge regions, non-simple polygons must be divided into simple polygons. That requires the integration of barrier-edges as part of the boundary of new simple polygons. Since this requirement is part of the meshing algorithm we are proposing in Sect. 4, beforehand, we need to introduce some definitions and prove some properties that will sustain the correctness of the algorithm.

Definition 3

Barrier-edge tip: A barrier-edge tip in a terminal-edge region R is a barrier-edge endpoint shared by no other barrier-edge/frontier-edge.

Figure 4 includes two polygons with barrier-edges; the barrier-edge tips are shown in green. Figure 4a shows a case of a polygon with one barrier-edge tip and Fig. 4b a case with two barrier-edge tips. We have observed that each point of the input data is an endpoint of a frontier-edge or barrier-edge. This means that terminal-edge regions have none isolated interior points. Theorem 1 demonstrates this property.

Fig. 4

Examples of non-simple polygons. Black lines are frontier-edges, dashed black lines are internal-edges and red edges are terminal-edges. a One barrier-edge and one tip b four barrier-edges and two tips tip

Theorem 1

Let $\Omega$ be a triangulation with the set of vertices V in general position. Then, each vertex v is an end-point of at least one of the frontier- or barrier-edges, i.e. there is no isolated interior points (vertices incident only to internal-edges).

Proof

: Let v be a vertex associated to the terminal-edge region R generated by the terminal-edge e and T the set of the triangles that share v. By contradiction, let us assume that v is an interior point of R as shown in Fig. 5. Since the triangles in T are part of R, they must share their longest-edge around v. Given that T is finite, there should exist a triangle $t_0$ (see Fig. 5) that shares their longest-edge with two triangles of R to maintain v interior point in R. This is not possible because a triangle has just one edge labeled as its longest-edge. This contradicts our assumption, so v has to be an endpoint of at least one frontier- or barrier-edge in R. Since triangles in $\Omega$ are distributed into terminal-edge regions without overlap [55], isolated points can not exist. $\square$

Fig. 5

The vertex in green is an interior point

It is worth mentioning Theorem 1 guarantees that the initial points used to represent the geometric domain and the ones inside the domain to fulfill point density requirements are vertices delimiting one or more polygons. Moreover, each internal-edge is a diagonal of one polygon. Therefore, interior-edges that contain barrier-edge tips as endpoints can be used to split a non-simple polygon into simple polygons.

Note that if the input points are not in general position, a region without a terminal-edge might appear. This degenerate region R occur when the algorithm labels all edges that share a vertex v as internal-edges. This case might happen if all triangles in R are equilateral and the algorithm labels each edge e sharing v as the longest-edge in only one of the triangles that share e. Then all edges that share v are internal-edges. This rare kind of case can be solved by assigning one edge with v as endpoint as longest-edge in the two triangles that share it. In this way, R is now a terminal-edge region.

4 The algorithm

In this section, we describe the main steps of the proposed algorithm, its computational cost and the data structure used for its implementation. The algorithm receives an initial triangulation as input, that can be generated by any known triangulator. The triangulation can be Delaunay or not, but we are using Delaunay triangulations because, several polygons of the mesh keep some angles of the triangles of the input triangulation. Since a Delaunay triangulation maximizes the minimum angle over all the possible triangulations for a point set, this angle will be a lower bound for the minimum angle of the generated polygonal mesh.

There are several correct and robust triangulators such as Detri2 [27] and Triangle [26] available for free. We are using Detri2 [27] to generate the constrained Delaunay triangulation needed as initial mesh. The whole process applied to the initial triangulation is divided in next three phases:

• 1. Label phase: Each edge is labeled as longest-, terminal- or frontier-edges to build terminal-edge regions. The algorithm also labels one triangle in each terminal-edge region as seed triangle used in the next phase to build each polygon.

• 2. Traversal phase: Generation of polygons from seed triangles. In this phase the frontier-edge vertices of a terminal-edge region are stored in counter-clock-wise (CCW) order to build a polygon. Non-simple polygons generated in this phase are sent to the reparation phase.

• 3. Reparation phase: Polygons with barrier-edges are partitioned into simple polygons.

4.1 Data structures

In this subsection, we describe the data structures used in our implementation. We have decided to use an indexed data structure with adjacencies as described in [57]. The purpose of the following representation is to have an easy and compact way to travel through all the faces of the triangulation and, in an implicit way, using a special order in the representation, to access their edges and neighbor triangles in CCW.

The triangulation is represented using three one-dimensional arrays for the vertices, triangles and neighbor triangles, respectively. Vertices are stored in pairs (x, y), where each two consecutive elements of the Vertex array are the coordinates x and y of a point. The Triangle array is a set of indices to the Vertex array. Each 3 consecutive values is a triangle. Since the algorithm needs to know the neighbor through each triangle edge, the Neighbor array stores the three indices of the neighbor triangles of triangle i at the locations $3i + 0$, $3i + 1$, $3i + 2$.

To facilitate the implementation of the algorithm, vertex indices in the Triangle array are ordered in such a manner that is easy to find out which is the neighbor triangle through each triangle edge. Figure 6a illustrates the connections of each array element. The first two point indices $3i+0$, $3i+1$ in the Triangle array is an edge of triangle i and this edge is shared with the triangle stored in the position $3i+2$ of the Neighbor array; the triangle edge defined by $3i+1$, $3i+2$ in the Triangle array is shared with the triangle stored in $3i+0$ in the Neighbor array and the triangle edge $3i+2$, $3i+0$ in the Triangle array with the triangle stored at $3i+1$ in Neighbor array. Triangle edges are stored implicitly: the green edge in Fig. 6b corresponds to the first one, the red edge is the second one and the blue the third one. These neighborhood relations can currently be generated as output by several tools such as Qhull [28], Triangle [26] and Detri2qt [27].

Fig. 6

Data structure: a relation between the vertex indices in the Triangle array and the triangle indices in the Neighbor array. b Triangle information stored in the data structure shown in a

The final mesh composed of simple polygons is also stored in one array, where each polygon includes first its number of vertices and then the vertex indices in CCW as shown in Fig. 7.

Data structures to store additional information needed only in one of the steps of the algorithm are mentioned in the respective subsection. It is worth mentioning here the representation of non-simple polygons since this information is used in two phases. Figure 8 shows an example of a polygon with two barrier edge tips. This kind of polygon is stored in an index array in the same way as a simple polygon in order CCW, and it is recognized as non-simple because there are repeated vertex indices. The same occurs with the seed list L, which is initialized in the Label phase with one triangle index per each terminal-edge region, and used in the Traversal phase to build polygons.

Fig. 7

Mesh array with three polygons

Fig. 8

Representation of a non-simple polygon as a set of vertex indices in CCW. Sequences 3–4–3 and 3–5–3 indicate the existence of barrier-edge tips

4.2 Label phase

The goal of the Label phase is to find frontier-edges, terminal-edges and seed triangles to build polygons in the next phase. The pseudo-code of this process is shown in Algorithm 1. The algorithm first cycles over each triangle of the initial triangulation (line 1) to compute which edge is the longest-edge and stores this edge index (one per each triangle) in a temporal array of size equal to the number of triangles; in the case of equilateral and isosceles triangles, the algorithm assigns randomly a size order to the equal length edges to avoid having a triangle that belongs to two terminal-edge regions at the same time.

Afterward, the algorithm does a second iteration over the edges (line 4). In case an edge e is not the longest-edge of any of the two triangles that share it (line 6), e is labeled as a frontier-edge. In case e is a terminal-edge (line 9), the algorithm stores the smallest index of the triangles that share it in the Seed list L. In the case of a boundary terminal-edge, the index of the unique triangle is stored.

The final result of this step is shown in Fig. 9b. The colorful triangles are the seeds used in the next phase to generate the polygons. It can also be observed that terminal-edge regions are delimited by frontier-edges.

Fig. 9

Label phase: a input Delaunay triangulation. b Solid lines are the frontier-edges, dashed lines are the internal-edges and colorful triangles are seed triangles

4.3 Traversal phase

In this phase, polygons are built and represented as a closed polyline as shown in Fig. 8. The main idea behind this phase is to travel through neighbor triangles, neighbors by internal-edges inside a terminal-edge region and save their frontier-edges as edges of the new polygon P in CCW. For this reason, the algorithm uses each triangle t inserted in the Seed list L as the starting triangle to build each polygon. The pseudo-code of this phase is shown in Algorithm 2.

From line 1 until line 13, the algorithm gets the first triangle t from the Seed list and initializes the variables according to the number of frontier-edges that t has. In case t has 3 frontier-edge edges, t is stored in the polygon P as a whole polygon. In case t has less than 3 frontier-edges, their endpoints are saved as the first points of P in CCW. In addition, the first vertex of P and t are saved in $v_\mathrm{{init}}$ and $t_\mathrm{{init}}$, respectively, to check when the polygon boundary is ready. It is also necessary to store the last added vertex in P in $v_\mathrm{{end}}$ to look for the e endpoint to be added. In case t has no frontier-edge (Line 10), the algorithm saves any vertex of t as $v_\mathrm{{init}}$ and $v_\mathrm{{end}}$, and t in $t_\mathrm{{init}}$. In the end, all vertices of t will be part of polygon boundary; then it does not matter which one is taken as the initial point. After the initialization, the algorithm travels to the next internal-edge neighboring triangle $t'$ that shares $v_\mathrm{{end}}$ with t. Three cases for $t'$ must be considered:

• 1. Line 15: The triangle $t'$ has just one frontier-edge e and this edge contains $v_\mathrm{{end}}$. Then e is stored in P and $v_\mathrm{{end}}$ is updated with the other e endpoint. The next triangle $t'$ is the non-visited internal-edge neighbor triangle that contains the new $v_\mathrm{{end}}$.

• 2. Line 19: The triangle $t'$ is an ear triangle (a triangle with 2 frontier-edges). In this case, both edges are stored in CCW in P and $v_\mathrm{{end}}$ is updated with last stored endpoint. The previously visited triangle is the new $t'$ because the other two triangles are neighbor by frontier-edges (i.e., they belong to other terminal-edge regions).

• 3. Line 23: The triangle $t'$ has no frontier-edge. $t'$ shares an internal-edge with the last visited triangle and with the other two neighbor triangles that can be visited. Just one of these two triangles contains the endpoint $v_\mathrm{{end}}$ as vertex, so that triangle is the new $t'$ (Fig. 10).

Fig. 10

Traversal phase. The green triangle is the seed triangle of this terminal-edge region. The labels indicate in which order each triangle was visited

Algorithm 2 is applied to each seed triangle and returns a polygon P. Note that triangles with no frontier-edges are visited three times, with one frontier-edge two times and with two frontier-edges one time; this is demostrated in Lemma 1. In case P has barrier-edge tips, the algorithm described in Sect. 4.4 is used to divide it into simple-polygons. A non-simple polygon can be easily detected by just checking the repetition of consecutive vertices in P: given three consecutive vertices of P, $v_i$, $v_j$ and $v_k$, if $v_i$ and $v_k$ are equal, then $v_j$ is a barrier-edge tip. In case P does not have barrier-edge tips, the polygon is saved as part of the mesh in the Mesh array.

Lemma 1

Each triangle is visited at most 3 times during the polygon construction from a terminal-edge region.

Proof

: By construction, the algorithm can only visit triangles through their internal edges. The worst case is when a triangle has three internal edges (no frontier-edges); then this triangle is visited once per internal edge, i.e., three times. In case of two-internal edges, the triangle is visited two times and in case of one internal-edge just 1 time. $\square$

4.4 Non-simple polygon reparation

As previously mentioned, some polygons generated in the Traversal phase are non-simple. In this section, we describe an algorithm to divide non-simple polygons into simple-ones using internal-edges containing barrier-edge tips as one of their end-points. Notice that a simple strategy could just be to remove barrier-edges and keep as polygon boundary only the frontier-edges. However, this approach would require to delete barrier-edge endpoints, which are vertices defined/inserted in the initial triangulation by the user/triangulation tool. We assume that all points are important. That is why, we propose a method to repair non-simple polygons without removing initial vertices.

The reparation process works similarly to the Label and Traversal phases but inside a non-simple polygon P. In short, the algorithm labels so many internal edges as frontier-edges until all barrier-edge tips are part of a polygon boundary and stores one seed triangle per each new polygon in a new Seed list $L_p$. After, those triangles are used as seed to generate the new polygons with the Algorithm 2. The internal-edges chosen to be new frontier edges are the ones that contribute to generate polygons of similar size.

The reparation algorithm is shown in Algorithm 3. For each barrier-edge tip $b_i$ in a polygon P (line 4), the algorithm computes first deg$(b_i)$, which is the number of incident internal-edges to $b_i$ inside the terminal-edge region. To facilitate this calculation, the algorithm uses an auxiliary array that associates to each vertex a triangle. If deg$(b_i)$ is odd then the algorithm labels the middle edge as frontier-edge; otherwise, the algorithm chooses any of the two middle edges as a new frontier-edge. In both cases, the two triangles that share the new frontier-edge are saved in the seed list $L_p$. From line 10 to line  14, each new simple polygon is built. A Bit array A, of size equal to the number of triangles of the input triangulation is used to avoid the generation of the same polygon more than once. The insertion of one or more seed triangles of the same new polygon in the seed list $L_p$ occurs when a terminal-edge region contains more than one barrier-edge tip. Each seed triangle stored in $L_p$ is set to 1 in A; the others are 0. When a polygon is built, each used triangle is set to 0 in A. Figure 11a shows an example of a non-simple polygon with three barrier-edge tips (vertices in green color). Figure 11b shows the internal-edges converted in new frontier-edges to delimit the new simple polygons and the six seed triangles stored in $L_p$. Figure 11c shows the four new polygons after the split and the seed triangles used to generate them.

It is worth mentioning that the number of polygons generated after the split is at most $(|B|+ 1)$, with $|B|$ the number of barrier-edge tips in a polygon P.

Lemma 2

Let $\Omega$ be the input triangulation and B the set of barrier edge tips in the polygon P. In the computation of deg$(b_i)$, $\forall b_i, b_i \in B$, each triangle t inside the terminal-edge region that generated P can be visited at most three times.

Proof

: By construction if a triangle t is not incident to a barrier-edge tip $b_i$, Algorithm 3 does not visit t during the computation of deg$(b_i)$. If t contains as vertex one, two or three barrier-edge tips, then t is visited one time per each barrier-edge tip. Since t has at most 3 barrier-edge tips then t is visited in the worst case 3 times for the computation of deg$(b_i)$. $\square$

Fig. 11

Example of a non-simple polygon split using barrier-edge tips. a Non-simple polygon. b Middle edges incident to barrier-edge tips labeled as frontier-edges (solid lines) and seed triangles (colorful triangles) stored in the seed list $L_p$ and marked as 1 in the A bit array. c The four new polygons without barrier-edge tips

4.5 Computational complexity analysis

In this section, we analyze the computational complexity of the whole algorithm. Let n be the initial number of points, m the number of triangles of the input triangulation, $m_i$ the number of triangles of the terminal-edge region $R_i$ used to generate the simple or non-simple polygon $P_i$

• 1. Label phase This phase uses three iterations of cost O(m), one to label longest-edges, one to identify terminal-edges and another to store seed triangles.

• 2. Traversal phase This phase calls Algorithm 2 to build one polygon simple or not simple. The construction of polygon $P_i$ has cost $O(m_i)$. Each triangle is visited three times by Lemma 1 in the worst case (when a triangle does not have frontier-edges). As each terminal-edge region covers the whole domain without overlapping, then this phase costs O(m).

• 3. Non-simple polygon reparation phase This phase calls Algorithm 3 to divide one non-simple polygon $P_i$ into simple ones. By Lemma 2, each triangle $t \in R_i$ is visited at most 3 times, so the computation of deg(b), $\forall b \in R_i$ is $O(m_i)$. The partition of $P_i$ into simple polygons has then a cost $O(m_i)$ because the new simple polygons do not overlap and the algorithm only travels inside their triangles. Finally, the cost to repair all non-simple polygons is bounded O(m).

As result, the computational complexity of the whole algorithm is O(n) ($m = O(n)$). With respect to the memory usage, the cost is O(n) too. The Vertex array has size 2n, the Triangle and Neighbor arrays have size 3n. The number of final polygons in the mesh is less than the number of triangles in the input triangulation, i.e., bounded by m.

4.6 Impact of the initial triangulation

As mentioned above, the polygons inside a Polylla mesh depend on the initial triangulation. Any triangulation can be used as input. Fig. 12 shows three different triangulations for the same point distribution generated using algorithms available in the 2D Triangulations package of the CGAL library [29]. Figure 12d is a Polylla mesh built from the triangulation generated by the incremental algorithm without edge-flips (Fig. 12a). The Polylla mesh in Fig. 12e was built from a regular triangulation [58] (a weighted triangulation) with random weights shown in Fig. 12b, f shows a Polylla mesh generated from the Delaunay triangulation drawn in Fig. 12c. As expected, the shape of the resulting polygons is notoriously different. In order to see the differences, Table 1 shows for each mesh, the minimum and maximum interior angle of both the input triangulation and the generated polygon meshes, the number of polygons and the average number of edges per polygon. It can be observed that polygon meshes have a minimum interior angle greater than the minimum angle of the corresponding triangulation. Since the Polylla algorithm joins triangles to generate polygons, the lower bound for the minimum interior angle of any polygon is the minimum angle of the input triangulation. In the case of maximum angles, the maximum angle of a Polylla mesh is usually larger than the maximum angle of the input triangulation because a Polylla’s polygons can be nonconvex polygons. It seems that Polylla meshes generated from Delaunay triangulations tends to contain less polygons and polygons defined with more edges than the ones obtained from other triangulations. Further research is necessary to probe these findings.

Fig. 12

Polylla meshes generated from different kind of initial triangulations over the same input points. Triangulations were generated using the 2D Triangulations package of CGAL library [29]. a Triangulation generated by the incremental algorithm, b regular triangulation generated using random weights, c Delaunay triangulation, d Polylla mesh generated from the triangulation a, e Polylla mesh generated from the triangulation (b), and f Polylla mesh generated from the triangulation (c)

Table 1 Geometric information of the Polylla meshes generated from different triangulations from the same point set (150 points)

It is worth to mention that since the Polylla algorithm takes as input a triangulation, it can process any geometry domain that can be triangulated. This includes complex geometries with holes as shown in Fig. 13. In particular, Fig. 13a shows a geometry specified as a planar straight line graph (PLSG) obtained from [26]. Figure 13a is a Polylla mesh generated from a constrained Delaunay triangulation of Fig. 13b. Fig. 13c shows a Polylla mesh from a refined conforming Delaunay triangulation of Fig. 13b. Grey polygons are holes. The algorithm considers the edges of the holes as border edges. Meshes generated from complex geometries representing Chilean geographic regions can be seen in Appendix A.

Fig. 13

Polylla mesh generated from the PLSG description of the Face taken from [26]. The edges of the initial triangulation are drawn using black and cyan colors. b Polygonal mesh obtained from the constrained Delaunay triangulation of the input geometry (26 vertices). c Polygonal mesh generated from a refined Delaunay triangulation with 220 vertices

5 Polylla meshes vs Voronoi based meshes

Currently, if polygonal meshes different from triangulations or quad meshes are required to solve some scientific or engineering problems, constrained Voronoi meshes are chosen. We believe that the polygonal meshes generated by Polylla can be an alternative to Voronoi meshes when researchers and engineers would like to model domains using arbitrary polygon shapes. That is why in this section we show standard statistics of these new polygonal meshes in contrast to constrained Voronoi meshes. The C++ implementation of Polylla used for the experiments can be downloaded from this repository².

The experiment was designed as follows: the domain is a square with a set of random points in its interior varying from $10^2$ to $10^6$. A tolerance $\pm \gamma$ is defined and used in case of a point p is too close to one square side; in that case the point p is inserted in the border edge. The statistics of the polygonal meshes generated by Polylla starting from Delaunay triangulations generated by using Detri2 [27] are summarized in Table 2. In the case constrained Voronoi meshes, Deldir [59] was used to generate the meshes and to obtain their mesh information. The statistics for the same initial points (sites) are presented in Table 3.

Table 2 Geometric information of Polylla mesh

Table 3 Geometric information of constrained Voronoi diagram

In Table 2, we can observe that over $10^4$ input points, the number of initial triangles per polygon is 6.5 and the number of vertices per polygon is 8.5, both values on average. The number of barrier-edge tips is less than $3\%$ of the number of points, so the reparation phase just adds less than $10\%$ of polygons to the mesh. If we compare Polylla meshes with the meshes generated from the Voronoi diagram, the constrained Voronoi meshes contain three times more polygons than our meshes. Each Voronoi region based polygon is delimited in average by six edges and Polylla polygons by eight edges. Moreover, the Polylla meshes use only the points given as input; in contrast, the Voronoi based meshes use new points, the Voronoi points, one per each triangle of the Delaunay mesh. Since the number of triangles is greater than the number of input points, the size of the Voronoi mesh is greater than the size of the Polylla mesh not only in terms of polygons, but also in terms of mesh points.

It is worth mentioning that a Polylla mesh does not need to insert extra-points at the boundary to fit the domain geometry; in contrast the constrained Voronoi mesh includes new points at the boundary/interfaces inserted while cutting the Voronoi regions that go outside the domain.

We have also evaluated the time performance of Polylla. The results shown in Fig. 14 were made on Patagón, a computer with two Intel Xeon Platinum 8260 of 2.4Ghz, located at the Universidad Austral de Chile [60]. The results are the average time of five program executions with same data-set in a different core. The time of each phase is included together with time to generate the initial triangulation. Of the three phases described in Sect. 4, the phase that takes less time is the non-simple polygon reparation phase. The main reason is that the number of terminal-edge regions with barrier edges is around 1% of the total number terminal-edges regions formed from random point sets as can be seen in Fig. 14. The time of the Label phase is higher than the time of the traversal phase. This can be explained due to the use of floating-point arithmetic to calculate the length of each edge and so to assign the proper label.

To compare the CPU time required to generate constrained Voronoi and Polylla meshes, we looked for free and open source tools. The CGAL library provides 2D Voronoi Diagram Adaptor package [61] to generate Voronoi diagrams, but this package does not provide a method to cut Voronoi regions against the domain boundary. So we implemented a function to do this process. In contrast, Detri2 [27] offers a robust method to generate constrained Voronoi meshes. Table 4 shows the cpu-times in seconds needed to generate polygonal meshes using Polylla, Detri2D and CGAL from 100,000, 500,000 and 1,000,000 points over a L-shape domain. Experiments were run in a CPU Intel(R) Core(TM) i5-9600K of 3.70GHz. Detri2d computes the CDT first and then the CVD from the CDT. That is why we included the time to generate the CDT separated from the generation of the CVD. The Polylla time includes only the time spent in the three phases that processes the input triangulation to generate the polygon mesh. The CGAl algorithm to generate the VD includes generation of the Delaunay triangulation first and from this triangulation computes the Voronoi Diagram. The CVD cost in CGAL is the sum of VD and CV. This preliminary comparison shows that the time to generate a CDT using Detri2d or CGAL plus the time Polylla takes to generate the polygonal mesh is much less than the time needed for generating a CVD either using Detri2 or the CGAl library. The main reason is that constrained Voronoi based meshing algorithms require to compute and insert new points (Voronoi points), to cut Voronoi regions and insert new boundary points. In contrast, the Polylla algorithm just needs to process the vertices, edges and triangles of the input triangulation. The domain boundary is already represented by some triangle edges.

Table 4 Time comparison, in seconds, of Polylla vs Constrained Voronoi Diagram (CDV) using Detri2 and CGAL. CDT is the time to generate a Constrained Delaunay Triangulation, VD is the time of generate Voronoi Diagram, CV is the time need to cut all regions of Voronoi Diagram and CVD is the total time of generate the Constrained Voronoi Diagram

Fig. 14

Time performance of the different algorithm phases. The label Polylla mesh indicates the time of the three phases

In Fig. 15 a qualitative comparison between a Polylla mesh and a constrained Voronoi mesh can be observed. Both meshes were generated from the same initial random point set. Fig. 15a shows the polygonal mesh generated by Polylla and Fig. 15b the constrained Voronoi mesh generated by Detri2qt. Some other examples of polygonal meshes generated for non convex domains are shown in Figs. 13 and 16.

Figure 16 shows polygonal meshes for an Unicorn example generated by both the Polylla (Fig. 16b) and Detri2qt (Fig. 16) tools. The initial triangulation and interior points are shown in Fig. 16a. As expected, the constrained Voronoi mesh contains more points (100 vertices) and polygons than the Polylla mesh as shown in Fig. 16. Just for a qualitative comparison, we used Polylla to generate a polygonal mesh from 100 vertices and this mesh is shown in Fig. 16d.

Fig. 15

Meshes generated from 1000 random points. a Polylla mesh. b Constrained Voronoi mesh generated with Detri2qt [27]

Fig. 16

Qualitative comparison using an Unicorn PLSG as input [62] a triangulation of unicorn PLSG with 36 vertices. b Polylla mesh includes exactly the 36 input vertices. c The constrained Voronoi mesh requires 100 vertices to model the same input. d Polylla mesh from a refined Delaunay triangulation with 100 vertices

6 Preliminary simulation results

In this section, we assess the Polylla meshes using the virtual element method (VEM) [1]. To this end, an L-shaped domain is considered. Figure 17 shows this domain meshed with a random and a semiuniform Polylla sample mesh. For comparison purposes, we also consider random and semiuniform Voronoi meshes (sample meshes are depicted in Fig. 18). The chosen problem is governed by the Laplace equation and its exact solution is given by [63]

$$\begin{aligned} u(x_1,x_2)=r^{2/3} \sin (2/3\,\theta ), \quad r=\sqrt{x_1^2+x_2^2}, \quad \theta (x_1,x_2)=\arctan (x_2/x_1). \end{aligned}$$

The boundary conditions are of Dirichlet type with the exact solution imposed on the entire domain boundary. The re-entrant corner of the L-shaped domain introduces a singularity in the solution that manifests itself as unbounded derivatives of u at the origin. The numerical solution (denoted by $u_h$) is assessed through its convergence with mesh refinements. Figs. 19 and 20 present the $L^2$ norm and the $H^1$ seminorm of the error, where it is shown that the VEM on Polylla (random and semiuniform) and Voronoi (random and semiuniform) meshes delivers accurate solutions with optimal convergence rates of 2 (for the $L^2$ norm) and 1 (for the $H^1$ seminorm).

The performance of VEM using Polylla (random and semiuniform) and Voronoi (random and semiuniform) meshes are compared in Fig. 21, where the $H^1$ seminorm of the error and the normalized CPU time are each plotted as a function of the number of degrees of freedom (DOF). The normalized CPU time is defined as the ratio of the CPU time of a particular simulation to the maximum CPU time found for any of the simulations that were run. Each of the four set of meshes (random Polylla, semiuniform Polylla, random Voronoi and semiuniform Voronoi) consists of four meshes of increasing number of degrees of freedom. Therefore, in total, there are sixteen meshes in the study.

The CPU time is measured from the reading of the mesh until the solution of the system of equations is ended. Each mesh is run ten times and the CPU time recorded is the average CPU time. From Fig. 21 it is observed that for equal number of degrees of freedom similar accuracy and computational cost are obtained for the four set of meshes.

Finally, for completeness of the presented numerical results, contour plots of the VEM solution on Polylla meshes are shown in Figs. 22 and 23 for the $u_h$ and ${\varvec{\nabla }}u_h$ fields, respectively.

Fig. 17

L-shaped domain meshed with a a random and b a semiuniform Polylla mesh

Fig. 18

L-shaped domain meshed with a a random and b a semiuniform Voronoi mesh

Note that random Polylla meshes (Fig. 17a) were generated from constrained Delaunay triangulation built over a L-shaped domain with points randomly generated in its interior. Semiuniform Polylla (Fig. 17b) meshes were generated from a conforming Delaunay triangulation using pygalmesh [5]. To generate the same number of triangles as the random mesh, an arbitrary maximum edge size constraint was given as input. The random (Fig. 18a) and semiuniform (Fig. 18b) Voronoi meshes were generated from the points (sites) of both the constrained Delaunay triangulation and the conforming Delaunay triangulation, respectively. Next, each infinite Voronoi region was intersected with the L-shaped domain to generate the constrained Voronoi mesh.

Fig. 19

$L^2$ norm and $H^1$ seminorm of the error using the VEM on random Polylla meshes (a and b, respectively), and on random Voronoi meshes (c and d, respectively)

Fig. 20

$L^2$ norm and $H^1$ seminorm of the error using the VEM on semiuniform Polylla meshes (a, b, respectively), and on semiuniform Voronoi meshes (c and d, respectively)

Fig. 21

Performance of the VEM using Polylla and Voronoi meshes. a $H^1$ seminorm of the error and b CPU time as a function of the degrees of freedom (DOF)

Fig. 22

Contour plots of the VEM solution for the u field. a Random and b semiuniform Polylla meshes

Fig. 23

Contour plots of the VEM solution for the ${\varvec{\nabla }}u$ field. a Random and b semiuniform Polylla meshes

7 Conclusions and ongoing work

We have presented Polylla, an algorithm to generate a new kind of polygonal mesh using terminal-edge regions. The proposed algorithm takes as input a triangulation with the required point density and generates a polygonal mesh without inserting new points. This generated mesh contains three times less polygons and half the number of points than the standard polygonal meshes based on the Voronoi diagram generated from the same input.

Some preliminary simulations were presented and the numerical results showed that the accuracy and computational cost of the VEM numerical solution using Polylla and Voronoi meshes are similar. We think that the advantage of Polylla meshes over Voronoi meshes lies in the mesh generation process, where, once the initial triangulation is available, Polylla meshes are simpler and faster to generate since these meshes do not require any addition or removal of vertices.

The ongoing work is devoted to adding more capabilities to Polylla. In particular, since the algorithm retains the underlying triangulation during the polygon construction, we plan to allow further refinements inside the polygonal mesh in a forthcoming version of Polylla. We also are in the process of developing an extension of the Polylla algorithm to polyhedral meshes using terminal edge-regions in 3D [56].

Appendix A: Complex geometries

This appendix presents some examples of Polylla meshes generated using cartography maps obtained from the Library of National Congress of Chile ³, and the library PyShp ⁴. This library was used to read the .shp files, generate the PSLGs and store the information in .poly files. Figure 24 is a Polylla mesh generated from the PSLG of the Los Lagos Region, Fig. 25 is a mesh of the Magallanes Region and Fig. 26 is a mesh of the Budi lake.

Fig. 24

Los Lagos Region, Chile. The .poly file contains 294,540 vertices and 294,242 segments. The initial triangulation was generated using triangle [26] with maximum area size of 100,000,000 as option. The resulting triangulation was a conforming Delaunay triangulation with 309,264 vertices, 309,305 triangles and 618,272 edges. The final Polylla mesh contains 309,264 vertices, 12,578 polygons and 321,534 edges

Fig. 25

Magallanes Region, Chile. The .poly file contains 1,130,733 vertices and 1,130,752 segments. The initial triangulation was generated using triangle [26] with maximum area size of 100,000,000 as option. The resulting conforming Delaunay triangulation contains 1,148,594 vertices, 1,182,133 triangles and 2,324,968 edges. The final Polylla mesh contains 1,148,594 vertices, 45,300 polygons and 1,186,451 edges

Fig. 26

Budi Lake, Araucanía Region, Chile. The .poly file contains 5794 vertices, 5794 constrained edges and 10 holes. The initial triangulation was generated using triangle [26] with maximum area size of 10,000 as option. The resulting conforming Delaunay triangulation contains 12,608 vertices, 19,406 triangles and 32,023 edges. The final Polylla mesh contains 12,608 vertices, 5169 polygons, 17,768 edges and 10 holes (Islands of the lake). Grey polygons are holes