The seven-triangle longest-side partition of triangles and mesh quality improvement

The seven-triangle longest-side partition of triangles and mesh quality improvement Alberto M´arqueza, Auxiliadora Moreno-Gonz´aleza,∗, ´Angel Plazab, Jos´eP. Su´arezc aDepartment of Applied Mathematics I, University of Seville, Spain bDepartment of Mathematics, University of Las Palmas de Gran Canaria, Spain cDepartment of Cartography and Graphic Engineering, University of Las Palmas de Gran Canaria, Spain ABSTRACT Keywords: Refinement Longest-edge based algorithms Improvement of mesh quality A new triangle partition, the seven-triangle longest-edge partition, based on the trisection of the edges is presented and the associated mesh quality improvement property, discussed. The seven-triangle longest-edge (7T-LE) partition of a triangle tis obtained by putting two equally spaced points per edge. After cutting off three triangles at the corners, the remaining hexagon is subdivided further by joining each point of the longest-edge of tto the base points of the opposite sub-triangle. Finally, the interior quadrangle is subdivided into two sub-triangles by the shortest diagonal. The self-improvement property of the 7T-LE partition is discussed, delimited and compared to the parallel property of the four-triangle longest-edge (4T-LE) partition. Global refinement strategies, combining longest-edge with self-similar partitions, are proposed, based on the theoretical geometrical properties. 1. Introduction In the context of finite element methodology, the adaptability of the mesh and the analysis of the approximation error are important issues to be addressed [1]. In recent years, many partitions and associated refinement and coarsening algorithms have been proposed and studied [2--7]. In the area of adaptive finite element methods, mesh refinement algorithms that maintain the non-degeneracy of the elements and the conformity and smoothness of the grid are certainly desirable. Non-degeneracy means that the minimum angle of the triangles is bounded away from zero when the partition or refinement is applied. Conformity refers to the requirement that the intersection of non-disjoint triangles is either a common vertex or a common edge. The smoothness condition states that the transition between small and large elements should be gradual. Non-degeneracy, conformity and smoothness are also desirable properties in adaptive tessellation of NURBS surfaces [8]. In this sense, Delaunay meshes have been widely used, since they avoid long, `skinny' triangles and produce the maximum possible smallestinternal angle of any triangle [9]. Refinement techniques are also used for enhancement of mesh obtained from trimmed NURBS surfaces. See an application of this in [10]. The number of triangles can be further increased/decreased depending on the application requirements. ∗Corresponding author. Tel.: +34954486482; fax: +34954488160. E-mail addresses: [email protected] (A. Márquez), [email protected] (A. Moreno-González), [email protected] (Á. Plaza), [email protected] (J.P. Suárez). Longest-edge based algorithms have been used with Delaunay triangulation for the quality triangulation problem [11,12], with details of the fractal properties of the meshes obtained by these algorithms also given [5,13,14]. Some refinement methods have had exact angle counts since they first existed [2,3,6,15] and, consequently, the non-degeneracy of the triangulation is proved. The four-triangle longest-edge (4T-LE) refinement algorithm proposed by Rivara [16], given that it is based on the longest-edge bisection, never produces an angle smaller than half the minimum original angle [16,17], whilst, moreover, revealing remarkable mesh quality improvement between certain limits, as recently studied in [18]. However, this mesh quality improvement depends on the geometry of the initial triangle as will be underlined herein. In search of a better mesh quality improvement by iterative partition of the mesh, in this paper, we have introduced a new triangle partition, the seven-triangle longest-edge (7T-LE) partition. This partition, first, positions two equally spaced points per edge and, then, the interior of the triangle is divided into seven sub-triangles in a manner compatible with the subdivision of the edges. Three of the new sub-triangles are similar to the original, two are similar to the new triangle also generated by the 4T-LE, and the other two triangles are, in general, better shaped. We compare the evolution of a standard quality measurement for the iterative application of the 7T-LE partition to an initial triangle, first with a Delaunay-type partition, and then using the 4T-LE partition. The paper is organized as follows: the 4T-LE partition and the selfimprovement property achieved via its application is summarized in Section 2. We go on to present the 7T-LE partition in Section 3, with some of its proven properties. Section 3 ends by comparing different strategies for partitioning a single triangle by combining longest-edge based partitions with self-similar partitions. Numerical experiments are provided in Section 4 proving that the new 7T-LE partition is comparatively better than the 4T-LE partition, and is also advantageous in many scenarios with respect to a 7-triangle local Delaunay-based partition. 2. Longest-edge triangular partitions Here the 4T-LE partition and its self-improvement is summarized. The section closes with an example illustrating the limits of the characteristics of improvement. In the following, for any triangle t, the edges and angles will be, respectively, denoted in decreasing order r1⩾r2⩾r3and ⩾⩾. Furthermore, t(,,)will be the class of similar triangles with angles ⩾⩾. Interchangeably, twill represent an element of the class t∈t(,,)or the class itself. Definition 1. The longest-edge (LE) partition of a triangle t0is obtained by joining the midpoint of the longest edge of t0with the opposite vertex (Fig. 1(a)). The 4-triangle longest-edge (4T-LE) partition is obtained by joining the midpoint of the longest edge to the opposite vertex and to the midpoints of the two remaining edges (see Fig. 1(b)). It should be noted here that in order to ensure the conformity over the mesh when local refinement based on the 4T-LE partition is used, two additional three-triangle (3T) partitions are applied along with the longest-edge (LE) partition [16]. The 3T partition of a triangle t is obtained by performing, first, the LE partition of t, and then, one of the two sub-triangles generated is further bisected by joining the midpoint of the longest-edge of twith the midpoint of the opposite edge. Fig. 2 shows these 3T partitions. The 3T partition of a triangle tin which the second longest-edge of tis also subdivided will be denoted here 3T-LE. Since the first 4T-LE partition of any triangle t0introduces two new edges parallel to the edges of t0, the same first 4T-LE partition of a single triangle t0produces two triangles similar to t0, and two (potentially) new similar triangles t1; and, consequently, the iterative 4T-LE partition of any triangle t0introduces (at most) one new dissimilar triangle per iteration [19]. See Fig. 3, in which two different situations for the 4T-LE partition are presented. On the left of the figure, the 4T-LE partition of triangle t1produces a new triangle t2. On the right, however, the generation of new triangles stops at the second stage of refinement. The iterative 4T-LE partition produces a finite sequence of `better' triangles satisfying the properties illustrated in the following diagram until triangle tNbecomes non-obtuse [19]: t0→t1→t2→...→tN (obtuse) (obtuse) (obtuse) (non-obtuse) 01>02>1N>N−1 01⩽0−12⩽1−2N⩽N−1−N Diagram 1. (From [19]) where iand iare, respectively, the smallest and the largest angles of triangle ti. The arrow emanating from triangle tito triangle ti+1 means that the (first) 4T-LE partition of triangle tiproduces the new dissimilar triangle ti+1. 2.1. Mesh quality improvement for the 4T-LE partition We refer the reader to [18] in which the self-improvement property of the 4T-LE partition has been studied in detail. The β0 r2 r3 α0 γ0 A C B r1 t0 t1t1 t0 Fig. 1. (a) LE partition of triangle t0, (b) 4T-LE partition of triangle t0. A C B t1 t0 A C B t0 t1 Fig. 2. Three-triangle partitions of triangle t0used in local refinement for assuring conformity. 3T-LE of t0at the right. t1 t1 t0 t0 t1 t0 t2 t2 t0 t1 t0 t1 Fig. 3. Two different situations. On the right, the generation of new triangles stops at the second stage of refinement. 0 5 10 15 0 30 60 90 120 150 REFINEMENT ITERATION ANGLE 4TLE MIN/MAX ANGLE EVOLUTIONS Fig. 4. Evolution of minimum and maximum angles of the new dissimilar triangles generated by the 4T-LE partition, one at a time. bounds of the minimum and second largest angles, when the 4T-LE partition is applied to an initial (obtuse) triangle, are detailed in [18]. By way of example, consider the initial triangle t0with angles (,,)=(1.95,32.595,145.455). The evolution of the smallest angle and largest angle for each of the new triangles generated by the 4T-LE partition is shown in Fig. 4. Therefore, the self-improvement property of the 4T-LE partition, as proven both experimentally and A C B t0t0 t0 t1t1tn1 tn1 Fig. 5. The 7T-LE partition of triangle t0=ABC. tn1 tn1 t0 t0 t0 t1 t1 Fig. 6. Two different 7T partitions of an obtuse triangle t0. (a) 7T-LE partition of t0. (b) 7T-D partition of t0. tn1 tn1 t0 t0 t0 t1 t1 tn1 t1 t0 A C A C M N B B Fig. 7. The 7T-LE partition and 3T-LE partition of an obtuse triangle t0=ABC. t0t0 t0 tn1 tn1 B C B C B C C′ M A AA Fig. 8. Two different ways of obtaining new triangles tn1, from triangle t0. (b) By doubling the shortest edge of t0. (c) By LE bisection of t0.tn1is the sub-triangle with acute angle at M. mathematically in [18], needs to be handled with caution, as the example clearly demonstrates. Given that the 4T-LE partition is based on the bisection of the edges, by locating midpoints on the edges of the triangle, we have introduced here a new triangular partition based on the trisection of φ B C BA C C′ C′ B′A ϕ Fig. 9. (a) |AB|<|BC|<|AC|and (b) <. the edges at equally spaced points. Our goal is to study the evolution of the shape of the triangles when this partition is iteratively applied, and to compare it with the behaviour given with the 4T-LE. 3. The 7T-LE partition In this section, a new longest-edge partition is presented. This partition is based on the trisection of the edges of the triangle, instead of the bisection of the edges as the 4T-LE. Definition 2. The 7-triangle longest-edge (7T-LE) partition of a triangle t0is obtained as follows: 1. Position two equally spaced points per edge and join them, using parallel segments, to the edges, at the points closest to each vertex (see Fig. 5(a)). 2. Join the two interior points of the longest edge of the initial triangle to the base points of the opposite sub-triangle in such a way that they do not intersect (see Fig. 5(b)). 3. Triangulate the interior quadrangle by the shortest diagonal (see Fig. 5(c)). It should be noted that, due to parallelism, the first three subtriangles obtained are similar to the initial one (t0), whereas the second two sub-triangles are similar to the first-class Rivara triangle (t1). In general, triangle t1is better shaped than triangle t0. This improvement has already been studied in [18] to which the reader is referred. Finally, the last two triangles are not given with the 4T- LE Rivara partition and, consequently, will be called here, tn1. Note also that the area of sub-triangles t0and t1is 1 9of the area of the initial triangle, whereas the area of each sub-triangle tn1is 2 9of the area of the initial triangle. Basing our hypotheses on the trisection of the edges, some other partitions may be considered. We present here one of these possibilities, also based on a local Delaunay triangulation: Definition 3. The 7-triangle Delaunay (7T-D) partition of a triangle t0is obtained as follows: 1. Position two equally spaced points per edge. t(i) B A C D BA C BA C D B A C D BA C D EE t(ii) t(iii) t(iv) Fig. 10. Sequence of dissimilar tn1triangles generated by the 7T-LE partition: (a) by doubling the shortest edge, (b) triangle ABD =t(i) is the first one with edge AD not been the shortest edge. (c)--(e) show the following non-similar triangles t(ii),t(ii) and t(iv), for the case in which BD is the longest edge of triangle ABD =t(i). 2. Triangulate the cloud of points using the Delaunay triangulation (see Fig. 6(b)). It should be noted that the 7T-D partition is not equivalent to the 7T-LE partition since the division of the interior hexagon depends upon the specific distribution of the distances between the vertices. See Fig. 6. 3.1. Mesh quality improvement for the 7T-LE partition Before studying in detail the self-improvement property of the 7T-LE partition, note that the new triangle tn1generated by the 7T- LE partition may also be seen as one of the triangles generated by the 3T-LE partition division, used in the local refinement associated with the 4T-LE partition. See Fig. 7 in which triangle t0, with vertices A, B, and C, is divided by the 7T-LE, and the extreme points of the diagonal of the interior quadrilateral are denoted by M, and N. Notice that, by parallelism, triangle AMN is similar to triangle ABC, and, therefore, the 7T-LE partition of triangle t0induces the 3T-LE partition of triangle AMN. Lemma 4. The number of dissimilar triangles arising in the iterative application of the 7T-LE partition to any initial triangle t0≡ABC is bounded. Proof. The 7T-LE partition of a triangle produces two new dissimilar classes of triangles per iteration. One of them is similar to the new (0,0) (0.5,0) (1,0) (a,b) α0 β2 γ1 α1 β1 α2 γ2 Fig. 11. 3T-LE partition of a random triangle. triangle generated by the 4T-LE partition. This triangle is noted by t1in Fig. 7(a). The other new dissimilar triangle is denoted by tn1 in Fig. 7(a). Notice that triangles t1and tn1appear also as a result I II III (0,0) (0.5,0)(-0.5,0) Fig. 12. The smallest angle of tn1is 2in region I,2in region II and 2in region III. RN RR (0,0) (0.5,0)(-0.5,0) Fig. 13. Regions RRand RN. of the 3T-LE partition of the initial triangle, see Fig. 7(b). Since the number of dissimilar triangles arising in the iterative application of the 4T-LE partition to any triangle t0is bounded [18,19], it is enough, here, to prove that the number of dissimilar triangles different from those generated by the 4T-LE partition, is also bounded. Let us presume that the edges of t0≡ABC verify that |BC|<|AC|<|AB|. The way to obtain a triangle similar to tn1, is to double the shortest edge BC and then join the new vertex C(note that in this situation C=B+2BC) to vertex A(see Fig. 8(b)): or the other equivalent, by carrying out an LE bisection of the original triangle and taking the acute sub-triangle generated (see Fig. 8(c)). These two possibilities will be taken into account in the discussion hereinafter. Therefore, in order to obtain the different triangles tn1generated by iterative application of the 7T-LE partition, we double the shortest edge BC successively, whenever the baseline AB is not the shortest edge of the triangle, until the last doubled edge becomes the longest Fig. 14. Self-similar partitions depending on the number of points per edge. (a) one point per edge. (b) Two points per edge. 4T-SS/9T-SS 7T-LE 4T-LE (0,0) (0.5,0)(-0.5,0) Fig. 15. Best partition for a triangle. one of the new triangle generated. Supposing that the last doubled edge is BC, the new edge BCis not the longest one, but AB, however, is the shortest one, that is |AB|<|BC|<|AC|, (see Fig. 9(a)). Then, we double the edge AB and now, we can see how, in Fig. 9(b), ACis the shortest edge. Therefore, if ABis the longest edge, the last doubled edge becomes the longest one of the new triangle. If not, we can see that angle =  BAC<= ABC, that is, the new angle defined by the last doubled edge and the shortest one, is smaller than in the previous situation so, at some point, this process must end and the last doubled edge becomes the longest one. Let us suppose, then, that, in our initial triangle ABC ≡t0, |BC|<|AC|<|AB|and when we double BC, and new point D=B+2BC is generated, in triangle ABD =t(i), edge BD is the longest one, (see Figs. 10(a) and (b)). There are now two possibilities: (1) If |AD|>|AB|, then the next new triangle produced by the 7T-LE partition, resulting from the LE bisection of triangle t(i), is triangle t0=ABC which has been previously considered, and there the process ends. (2) In the other case, i.e. if |AD|<|AB|<|BD|, then the next new triangle produced by the 7T-LE partition, resulting from the LE bisection of triangle t(i), is triangle t(ii) =ACD. (See Fig. 10(c)). In this triangle, |CD|=|BC|<|AC|, so there are three cases to study: (a) First, if we presume that |CD|<|AC|<|AD|, then we double edge CD and we obtain triangle t(i) again. (b) Let us now presume that |CD|<|AD|<|AC|. Then we divide the longest edge AC and triangle t(iii) =CDE is obtained. See Fig. 10(d). It is easy to see that the shortest-edge of this new Table 1 Sequences of dissimilar triangles obtained by the 4T-LE and 7T-LE partitions It. n4T-LE triangles no. of dissimilar triangles 15 7T-LE triangles no. of dissimilar triangles 7 nnnnnn Test 1: Initial triangle t0=(145.455,32.595,1.950) 0 145.455 32.595 1.950 145.455 32.595 1.950 1 143.292 34.545 2.164 143.291 32.595 4.114 2 140.885 36.708 2.407 138.198 32.595 9.206 3 138.200 39.115 2.684 123.933 32.595 23.472 4 135.202 41.800 2.998 77.683 69.721 32.595 5 131.850 44.798 3.351 69.721 59.152 51.125 6 128.107 48.150 3.743 84.036 59.152 36.810 7 123.937 51.893 4.170 69.721 59.152 51.125 8 119.316 56.063 4.621 9 114.235 60.684 5.081 10 108.715 65.765 5.520 11 102.811 71.285 5.904 12 96.618 77.189 6.193 13 90.266 83.382 6.352 14 89.734 83.907 6.359 15 90.266 83.382 6.352 It. n4T-LE Triangles no. of dissimilar triangles 11 7T-LE Triangles no. of dissimilar triangles 8 nnnnnn Test 2: Initial triangle t0=(173.972,5.423,0.605) 0 173.972 5.423 0.605 173.972 5.423 0.605 1 173.216 6.028 0.756 173.215 5.423 1.361 2 172.245 6.784 0.971 170.949 5.423 3.627 3 170.952 7.755 1.293 153.689 20.887 5.4230 4 169.148 9.048 1.804 144.928 20.887 14.183 5 166.462 10.852 2.686 102.858 56.254 20.887 6 162.066 13.538 4.396 78.056 56.254 45.689 7 153.735 17.934 8.331 81.241 56.254 42.504 8 133.923 26.265 19.812 78.056 56.254 45.689 9 84.274 49.648 46.077 10 95.726 43.599 40.676 11 84.274 49.648 46.077 Test problem 1 and test problem 2. triangle is CE, so we double it, and we obtain triangle t(ii) again. (c) Finally, we must consider |AD|<|CD|<|AC|. As in the previous case, we divide AC but, now, we obtain triangle t(iv) =ADE. (See Fig. 10(d).) In this triangle, AE is the shortest-edge, so we double it and we obtain triangle t(ii) again.  3.2. Comparison of the 4T-LE and 7T-LE partition for a random triangle A geometric diagram is constructed as follows [20]: (1) for a given triangle or sub-triangle, the longest edge is scaled to have unit length. This forms the base of the diagram. (2) It follows that the set of all triangles is bounded by this horizontal segment (longest edge), defined by the points (0,0),(1,0), and by two bounding exterior circular arcs of unit-radius, centered, respectively, at (1,0)and at (0,0), as shown in Fig. 11. Note also that, by reflection around the vertical line x=1 2,itis enough to consider the left half of the diagram, which is equivalent to positioning the smallest angle at point (1,0)and the second largest angle at point (0,0). Our measurement of triangle quality, in this section, will be the smallest angle. For each random apex into the geometric diagram, we compare R, the smallest angle of the Rivara triangle with N, the smallest angle of the new triangle obtained in the 7T-LE partition. In this situation, there are regions where either Ror Nis better. These regions will be denoted, respectively, by RRand RN. First of all we must study which of the angles in triangle tn1is the smallest. By applying the Law of Sines, we can see that N=2if a2+b2<1 22and a< 1 4, N=2if a−1 22 +b2<1 22and a> 1 4and N=2in the rest of cases,that is,if a2+b2>1 22 and a−1 22 +b2>1 22. These three possibilities correspond respectively to regions II,III and Iin Fig. 12. Now, we compare Nwith 1,1and 1. In region Iwe obtain that 1is always smaller than 2,soN>R. In region II we obtain that 1is always smaller than 2so N>Rtoo. Finally, in region III, we find that 2is always smaller than 1and 1and is smaller than 1when (a−1)2+b2<1 2, so, only in this case, N<R.InFig. 13,we can see that regions RRand RNare separated by the circumference centered at (1,0)and with radius 1/√2. So if we compare the area covered by both regions, we obtain that the 7T-LE partition is better than the 4T-LE partition in 89% of the cases (more precisely, the areas of both regions are A(RR)=0.07135 and A(RN)=0.6486). Finally, notice that similar partitions of acute triangles are better than longest-edge partitions. Fig. 14 shows similar partitions of an acute triangle, depending on the number of the points per edge. In Fig. 15, we can see the rules which allow us to decide which of the various partitions to use. If (a −1)2+b2<1 2, we choose 4T-LE partition. If (a−1)2+b2>1 2and (a−1 2)2+b2<(1 2)2, we choose 7T- LE partition: and if (a −1 2)2+b2>(1 2)2, we choose the self-similar partition. Table 2 Sequences of dissimilar triangles obtained by the 4T-LE and 7T-LE partitions It. n4T-LE triangles---no. of dissimilar triangles 8 7T-LE triangles---no. of dissimilar triangles 7 nnnnnn Test 3: Initial triangle t0=(169.900,8.572,1.527) 0 169.900 8.572 1.527 169.900 8.572 1.527 1 167.721 10.100 2.180 167.719 8.572 3.708 2 164.371 12.279 3.349 158.613 12.814 8.572 3 158.625 15.629 5.747 125.395 41.790 12.814 4 146.921 21.375 11.704 106.818 41.790 31.391 5 117.268 33.079 29.652 75.424 62.784 41.790 6 63.237 62.732 54.031 73.181 62.784 44.033 7 116.763 33.270 29.967 75.424 62.784 41.790 8 63.237 62.732 54.031 It. n4T-LE triangles---no. of dissimilar triangles 4 7T-LE triangles--no. of dissimilar triangles 4 nnnnnn Test 4: Initial triangle t0=(114.624,54.900,10.475) 0 114.624 54.900 10.475 114.624 54.900 10.475 1 102.073 65.376 12.551 102.074 54.900 23.254 2 88.250 77.927 13.824 74.624 54.900 50.475 3 91.750 74.623 13.627 86.500 54.900 38.598 4 88.250 77.927 13.824 74.624 54.900 50.475 5 6 Test problem 3 and test problem 4. It should be noted that for a complete specification of local refinement based on the 7T-LE partition, there is a need to define how to achieve the conformity of the mesh. This will be tackled in a forthcoming paper [21]. 4. Numerical examples In this section, we present two different experiments. First, some test triangles also studied by Rivara and Iribarren in [19] and Plaza et al. in [18], were chosen to compare the evolution of the triangles generated by the 4T-LE partition with the new triangles generated by the 7T-LE partition. Second, we draw a comparison between the 7T-LE partition and the 7T-Delaunay partition. 4.1. The 7T-LE versus 4T-LE for mesh quality improvement Although we have already underlined the different behaviour with respect to mesh quality improvement given by the 7T-LE partition and the 4T-LE partition, here we present some numerical examples for different initial triangles t0.Tables 1 and 2show four test problems in which the sequence of dissimilar triangles are obtained by the 4T-LE and by the 7T-LE partition. Note that the new triangles generated by the 7T-LE partition are better shaped than the corresponding triangles generated by the 4T-LE partition. However, in test problems 2 and 3, the last (acute) triangles generated by the 4T-LE partition are better (in terms of the minimum angle) than the last new triangles generated by the 7T-LE. For a visual comparison of the evolution of the triangles, see Fig. 18. In order to visually compare the better improvement achieved by means of the 7T-LE partition, see Fig. 16, in which, and for example test 1, the evolution of the smallest and largest angles for each of the new triangles generated by the 7T-LE partition is shown. The initial triangle is t0=(,,)=(1.95,32.595,145.455)as in Rivara and Iribarren [19]. Compare the evolution of these angles with the evolution of the triangles generated by the 4T-LE partition given in Fig. 4 at page 7. For a better understanding of the self-improvement property of the 4T-LE partition, and the limits of this property as given in this paper, the successive triangles obtained have been normalized 01015 0 30 60 90 120 150 REFINEMENT ITERATION ANGLE 7T MIN/MAX ANGLE EVOLUTIONS 5 Fig. 16. Evolution of minimum and maximum angles of the new triangles generated by the 7T-LE partition, one at a time, for example test 1: t0=(145.455,32.595,1.950). to share the longest edge. Fig. 17 shows the triangles obtained by the 4T-LE and by the 7T-LE partition in the first test problem. Since all the triangles have been represented with longest edge on vertices (0,0)and (0,1), the evolution of the new triangles generated by the 7T-LE partition vs. the triangles generated by the 4T-LE partition can be observed, at a glance, from the diagrams in Fig. 18, where the third vertices are joined by lines, from bottom to top. It should be noted that, in the case of the last triangles generated by the 7T-LE partition in these tests, it would seem that the largest of the smallest angles generated does not depend upon the geometry of the initial triangle considered. This contrasts sharply with the situation for the 4T-LE partition, in which these angles improve, but within certain limits, depending upon the values of the angles of the initial triangle. 0 0.2 0.4 0.6 0.8 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 4T-LE New triangles generation 0 0.2 0.4 0.6 0.8 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 7T New triangles generation 1 2 3 4 5 6 Longest-edge Longest-edge Height Height Fig. 17. Evolution of dissimilar triangles of example test 1. 0 0.2 0.4 0.6 0.8 1 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 0.2 0.4 0.6 0.8 1 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 0.2 0.4 0.6 0.8 1 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0 0.2 0.4 0.6 0.8 1 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 Longest-edge Height Longest-edge Height Longest-edge Height Longest-edge Height Fig. 18. Evolution of the triangles given by the 4T-LE partition (solid line) vs. 7T-LE partition (dashed line). (a) Example test 1. (b) Example test 2. (c) Example test 3. (d) Example test 4. In order to experimentally check this conjecture, we carried out the following computational experiment. Select a point (x, y) within the mapping domain comprised the horizontal segment of extreme points (0,0)and (1,0), and the unit circular arcs which centre at these extreme points. Point (x, y) defines the apex of a target triangle with additional vertices at (0,0)and (1,0). For this triangle, 7T-LE division is successively applied as long as a new dissimilar tn1triangle appears. This means that we recursively apply 7T-LE and stop when the shapes of new generated triangles are the same as those already generated in previous refinement step. The number of such refinements to reach termination defines the number of dissimilar triangles associated with the initial triangle, and this numerical value is assigned to the initial point (x, y) chosen. This process is progressively applied to a large sample of triangles 0 0.2 0.4 0.6 0.8 1 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 2 4 6 8 10 12 14 16 2 3 4 5 6 7 LONGEST-EDGE HEIGHT 0 0.2 0.4 0.6 0.8 1 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 2 4 6 8 10 12 14 16 2 3 44 556 6 7 18 7 LONGEST-EDGE HEIGHT Fig. 19. Dissimilar triangle classes generated by computer experiment for the 7T-LE (a) vs. 4T-LE partition (b). Fig. 20. Two different initial triangulations. (a) Good quality mesh. (b) Bad quality mesh. (points) uniformly distributed over the domain. Finally, we graph the respective values of dissimilar triangles in a corresponding colour map to obtain the result in Fig. 19(a). The same experiment for the 4T-LE partition is shown in Fig. 19(b). It should be noted that the dark blue region in Fig. 19 corresponds to the region in which all the trajectories end, with total independence of the initial position. Therefore, for the 7T-LE partition, a lower bound for the maximum of the smallest angles for triangles tn1is =30◦corresponding to the apex with x=1 4, or the apex with x=3 4. Note also that the smallest angle in each of the regions generated in this way, is bounded from below with total independence of the initial point of the respective trajectories. This is a remarkable feature in comparison with the evolution of the angles for the 4T-LE partition. In the 4T-LE partition, these lower bounds depend on the geometry of the initial triangle. See [18] for details on the evolution of the angles when the 4T-LE partition is recursively applied. Also observe the evolution of the minimum angles in Tables 1 and 2. 4.2. A comparative study of two seven-triangle partitions Here we show a numerical comparison of the seven-triangle partitions previously presented. Namely, we apply these partitions to an initial (good quality) Delaunay mesh, and to a (poor quality) initial pentagonal mesh. See Fig. 20. For a comparison of the quality measurement evolution when each partition is globally applied, the mean value of the quality measurement has been calculated. Bearing in mind that for each triangle t, the quality measurement is defined by (t) =4A√3 l2 1+l2 2+l2 3 102103104105106 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Triangle measure quality for the refined meshes # Triangles Triangle quality 7T-LE 7T-D 4T-LE 102103104105106 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 Triangle measure quality for the refined meshes # Triangles Triangle quality 7T-LE 7T-D 4T-LE Fig. 21. Evolution of mesh quality. (a) Good quality mesh. (b) Bad quality mesh. where Ais the area of t, and l1,l2and l3the lengths of the sides of the triangle. If (t) > 0.6, triangle tis acceptable quality-wise. For the equilateral triangle =1 where l1=l2=l3=4A√3 3, see [4].It