Covariance edges matrix of geometric elements

In this paper, we introduce a new matrix associated with polygons and polyhedrons, namely the covariance edges matrix. We show that, for a regular polygon or polyhedron the corresponding matrix is proportional to the identity of size two or three. Based on this fact, we propose, as an application, several algebraic shape quality measures for convex polygons or polyhedrons. Furthermore, this matrix may be related to the metric of a simplex. Future studies will be devoted to the definition of the covariance edges matrix for higher elements and real applications to mesh optimisation.

Introduction

The resolution of physical phenomena formulated by partial differential equations using the finite element method requires a regular mesh (in the isotropic case) specifically for the convergence of the method. General discussions about mesh quality measures can be found in [1.2]. To quantify this regularity several shape quality measures have been introduced in [3,4] using various approaches and compared in [5-12] for simplexes in 2D and 3D. Many of them are implemented in the Verdict library [13].

Among all the possible definitions let us notice the radius ratio (or sometimes called aspect ratio) [14]:

$\rho \mathrm{<mo>=</mo>}d\frac{r_{\text{in}}}{r_{\text{out}}}$

Where d is the dimension of space and r_in, r_out, are respectively the inradius and the circumradius of the simplex. Another well-known quality metric is the mean ratio n [5] (explicitly used in [15]) which was already used in [16] and redefined in [17]:

$\eta \mathrm{<mo>=</mo>}\{\begin{array}{cc}\frac{4\sqrt{3}A}{{\displaystyle \sum _i}{l}_i^2}& \text{in2D}\\ \frac{12\sqrt[3]{9V^2}}{{\displaystyle \sum _i}{l}_i^2}& \text{in3D}\end{array}\text{ (1)}$

Those two measures are compared in [18] and used for instance in [19].

In [9] the author define a new method to unify various mesh quality metrics using an algebraic approach.

In this paper, we introduce the covariance edges matrix which allows us to characterise the regularity of the mesh elements (polygons and polyhedrons). By analysing the eigenvalues of this matrix we define several shape quality measures for convex elements.

Covariance edges matrix

Let p be a polygon or a polyhedron in R^d (d = 2 or d = 3) with n edges and let denote its edge column vector by $e_i\mathrm{<mo>=</mo>}\left(\begin{array}{c}{e}_{i\mathrm{,1}}\\ ⋮\\ e_{i\mathrm{,}d}\end{array}\right)$ as in Figure 1. For our application, we can set ei = vj - vj or ei = vj′ - vj with vj and vj′ the two vertices of the edge ei.

Following [17,20], the covariance edges matrix N associated to P is defined as:

$\mathcal{N}\mathrm{<mo\; stretchy="false">(</mo>}P\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}{e}_i{e}_i^T\mathrm{.}\text{ (2)}$

Each eiei^T is a symmetric rank-1 covariance matrix associated with an edge i of P. For a polyhedron in 3D, these matrices are:

$e_i{e}_i^T\mathrm{<mo>=</mo>}\left(\begin{array}{ccc}{e}_{i\mathrm{,1}}^2& e_{i\mathrm{,1}}{e}_{i\mathrm{,2}}& e_{i\mathrm{,1}}{e}_{i\mathrm{,3}}\\ e_{i\mathrm{,1}}{e}_{i\mathrm{,2}}& e_{i\mathrm{,2}}^2& e_{i\mathrm{,2}}{e}_{i\mathrm{,3}}\\ e_{i\mathrm{,1}}{e}_{i\mathrm{,3}}& e_{i\mathrm{,2}}{e}_{i\mathrm{,3}}& e_{i\mathrm{,3}}^2\\ & & \end{array}\right)\mathrm{.}$

As stated previously, we notice that each eiei^T and N does not depend on the direction (order of starting and ending point) of the vector ei.

For regular polygons (Lemma 7) or some polyhedrons (tetrahedrons in Lemma 14, cubes in Lemma 15, prisms in Lemma 16, and octahedrons in Lemma 18) we will show the regularity lemma:

$\mathcal{N}\mathrm{<mo\; stretchy="false">(</mo>}P\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{h}^2\frac{n}{d}{I}_d\mathrm{,}\text{ (3)}$

Where h is the length of all edges, X is the dimension of the space (2 or 3), and ld is the identity matrix in R^d. Besides, we will show (Lemma 17) that for a regular pyramid, this matrix is only diagonal on some basis (and not proportional to the identity). However, the regularity of the pyramid can be obtained by completing the pyramid to obtain an octahedron (see Lemma 19).

Hence, for a regular polygon or specific polyhedron, the covariance matrix has one eigenvalue of multiplicity d. Based on the invariants of the covariance edges matrix we can thus define several measures to quantify the gap between the eigenvalues for a general polygon or a polyhedron in order to obtain the corresponding shape quality measure.

At first, we developed some properties of N. These properties are used to prove the above regularity lemma. Then, we proposed shape quality measures.

Properties of the covariance edges matrix

In this section, some properties of the covariance edges matrix are given, namely the positive definiteness, the geometric invariants, and the commutativity with orthogonal matrices which keeps the polygon or polyhedron invariant. These properties will then be used to prove the regularity lemma in 2D and 3D.

Before the lemmas, we start with a remark that will be useful for the prisms and pyramids.

Remark 1: A matrix proportional to the identity matrix (ld) is invariant by a change of basis. This is not the case for a general diagonal matrix such as:

$M\mathrm{<mo>=</mo>}\left(\begin{array}{ccc}a& 0& 0\\ 0& b& 0\\ 0& 0& c\end{array}\right)$

General properties

Lemma 1: N is a symmetric positive-definite matrix.

Proof. N is symmetric by construction. Let X be a non-zero vector, we have:

$X^T\mathcal{N}X\mathrm{<mo>=</mo>}{X}^T{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}{e}_i{e}_i^{T}X$

$\mathrm{<mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}{X}^T{e}_i{e}_i^{T}X$

$\mathrm{<mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}{\mathrm{<mo\; stretchy="false">(</mo>}{e}_i^{T}X\mathrm{<mo\; stretchy="false">)</mo>}}^T\mathrm{<mo\; stretchy="false">(</mo>}{e}_i^{T}X\mathrm{<mo\; stretchy="false">)</mo>}$

$\mathrm{<mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}{\mathrm{<mo\; stretchy="false">(</mo>}{e}_i\cdot X\mathrm{<mo\; stretchy="false">)</mo>}}^2\ge 0$

And X^TNX = 0 implies that X must be orthogonal to all ei which is only possible with X = 0, so X^TNX > 0.

Lemma 2 (Commutativity with special orthogonal matrices): Let Q be an orthogonal matrix that defines a bijective mapping between the edges. That is to say such that Qei = eσ(i) with a permutation.

Q commutes with N.

Proof.

$\begin{array}{ll}Q\mathcal{N}{Q}^T\hfill & \mathrm{<mo>=</mo>}Q\left({\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}{e}_i{e}_i^T\right)Q^T\hfill \\ \hfill & \mathrm{<mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}\mathrm{<mo\; stretchy="false">(</mo>}Q{e}_i\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}Q{e}_i{\mathrm{<mo\; stretchy="false">)</mo>}}^T\hfill \\ \hfill & \mathrm{<mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}{e}_{\sigma \mathrm{<mo\; stretchy="false">(</mo>}i\mathrm{<mo\; stretchy="false">)</mo>}}{e}_{\sigma \mathrm{<mo\; stretchy="false">(</mo>}i\mathrm{<mo\; stretchy="false">)</mo>}}^T\hfill \\ \hfill & \mathrm{<mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}{e}_i{e}_i^T\hfill \\ \hfill & \mathrm{<mo>=</mo>}\mathcal{N}\hfill \end{array}\text{ (4)}$

Which leads to QN = NQ as Q^-1 = Q^T because Q is an orthogonal matrix.

Example 1: An example of such Q for a regular polygon in 2D is the rotation matrix of angle ${\theta }_n\mathrm{<mo>=</mo>}\frac{2\pi }{n}$ where n is the number of edges. Using, this rotation leads to Qei = ei+1 for 0 ≤ i < n with en := e0.

Link with the metric of simplex: In the case of a simplex (triangle in 2D and tetrahedra in 3D), one may find a link between the covariance edge matrix N and the metric of the element M. This matrix is such that ei^TMei = 1. Besides in [17,20], they show that:

$ℳ\mathrm{<mo>=</mo>}\frac{d+1}{2}{\mathcal{N}}^{-1}$

Properties in 2D: From Lemma 1, N is symmetric. In this section, we will denote N as:

$\mathcal{N}\mathrm{<mo>=</mo>}\left(\begin{array}{cc}a& b\\ b& c\end{array}\right)\mathrm{<mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}\left(\begin{array}{cc}{e}_{i\mathrm{,1}}^2& e_{i\mathrm{,1}}{e}_{i\mathrm{,2}}\\ e_{i\mathrm{,1}}{e}_{i\mathrm{,2}}& e_{i\mathrm{,2}}^2\end{array}\right)\text{ (5)}$

First, the computations of the two invariants (trace and determinant) are made, then we use the commutativity from Lemma 2 to prove the regularity of Lemma 7 already stated in (3).

Invariants in 2D: For d = 2, the two invariants (trace and determinant) of the covariance edges matrix N are linked to the squared edge length and the squared area of all parallelograms made up of two different edges as stated in Lemmas 3 and 4.

Lemma 3 (Invariants in 2D: trace): For d = 2, the trace of the covariance edges matrix N is:

$tr\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}\parallel e_i{\parallel }^2\text{ (6)}$

Proof.

$\begin{array}{ll}tr\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}\hfill & \mathrm{<mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}\mathrm{<mo\; stretchy="false">(</mo>}{e}_{i\mathrm{,1}}^2+e_{i\mathrm{,2}}^2\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}\parallel e_i{\parallel }^2\hfill \\ \hfill & \mathrm{<mo>=</mo>}{\lambda }_1+{\lambda }_2\hfill \end{array}$

Lemma 4 (Invariants in 2D: determinant): For d = 2, the determinant of the covariance edges matrix N is:

$\text{det}\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{0\le i\mathrm{<mo><</mo>}j\mathrm{<mo><</mo>}n}}{\left|\begin{array}{cc}{e}_i& e_j\end{array}\right|}^2\text{ (7)}$

Proof.

$\begin{array}{ll}\text{det}\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}\hfill & \mathrm{<mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}\mathrm{<mo\; stretchy="false">(</mo>}{e}_{i\mathrm{,1}}^2\mathrm{<mo\; stretchy="false">)</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}\mathrm{<mo\; stretchy="false">(</mo>}{e}_{i\mathrm{,2}}^2\mathrm{<mo\; stretchy="false">)</mo>}-{\left({\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}\mathrm{<mo\; stretchy="false">(</mo>}{e}_{i\mathrm{,1}}{e}_{i\mathrm{,2}}\mathrm{<mo\; stretchy="false">)</mo>}\right)}^2\hfill \\ \hfill & \mathrm{<mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}\mathrm{<mo\; stretchy="false">(</mo>}{e}_{i\mathrm{,1}}^2{e}_{i\mathrm{,2}}^2\mathrm{<mo\; stretchy="false">)</mo>}+{\displaystyle \sum _{i\ne j}}\mathrm{<mo\; stretchy="false">(</mo>}{e}_{i\mathrm{,1}}^2{e}_{j\mathrm{,2}}^2\mathrm{<mo\; stretchy="false">)</mo>}\hfill \\ \hfill & -\left[{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}\mathrm{<mo\; stretchy="false">(</mo>}{e}_{i\mathrm{,1}}^2{e}_{i\mathrm{,2}}^2\mathrm{<mo\; stretchy="false">)</mo>}+2{\displaystyle \sum _{0\le i\mathrm{<mo><</mo>}j\mathrm{<mo><</mo>}n}}\mathrm{<mo\; stretchy="false">(</mo>}{e}_{i\mathrm{,1}}{e}_{i\mathrm{,2}}{e}_{j\mathrm{,1}}{e}_{j\mathrm{,2}}\mathrm{<mo\; stretchy="false">)</mo>}\right]\hfill \\ \hfill & \mathrm{<mo>=</mo>}{\displaystyle \sum _{0\le i\mathrm{<mo><</mo>}j\mathrm{<mo><</mo>}n}}{\mathrm{<mo\; stretchy="false">(</mo>}{e}_{i\mathrm{,1}}{e}_{j\mathrm{,2}}-e_{j\mathrm{,1}}{e}_{i\mathrm{,2}}\mathrm{<mo\; stretchy="false">)</mo>}}^2\hfill \\ \hfill & \mathrm{<mo>=</mo>}{\displaystyle \sum _{0\le i\mathrm{<mo><</mo>}j\mathrm{<mo><</mo>}n}}{\left|\begin{array}{cc}{e}_i& e_j\end{array}\right|}^2\hfill \\ \hfill & \mathrm{<mo>=</mo>}{\lambda }_1{\lambda }_2\hfill \end{array}$

Remark 2: The sum (7) is composed of the area of all parallelograms made with two different edges. In the case of a triangle, this sum may be simplified to:

$\text{det}\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>3<mo\; stretchy="false">(</mo>2<mo>|</mo>}T{\mathrm{<mo>|</mo><mo\; stretchy="false">)</mo>}}^2$

with |T| the area of the triangle T.

Invariances by isometric transformations in 2D: In Lemmas 5 and 6, we show the form of the covariance edges matrix when the polygon is invariant by reflection or rotation.

Lemma 5 (Effects of 2D reflections): Consider a polygon P in 2D. If this polygon is invariant by a reflection then the covariance edges matrix is diagonal.

Proof. In 2D the two main reflections are:

$Q_x\mathrm{<mo>=</mo>}\left(\begin{array}{cc}1& 0\\ 0& -1\end{array}\right)Q_y\mathrm{<mo>=</mo>}\left(\begin{array}{cc}-1& 0\\ 0& 1\end{array}\right)$

From Lemma 2, we know that Q_XN = NQ_X, it leads to:

$Q_x\mathcal{N}\mathrm{<mo>=</mo>}\mathcal{N}{Q}_x\Rightarrow b\mathrm{<mo>=</mo>0}$

The same computations can be done with Q_Y and we have in both cases:

$\mathcal{N}\mathrm{<mo>=</mo>}\left(\begin{array}{cc}a& 0\\ 0& c\end{array}\right)$

Lemma 6 (Effects of 2D rotations): Consider a polygon P in 2D. If this polygon is invariant by a rotation of angle θ (different of 0[]) then the covariance edges matrix is proportional to the identity:

$\mathcal{N}\mathrm{<mo>=</mo>}a{I}_2$

Proof. Let Q be the rotation matrix of angle θ which let invariant P:

$Q\mathrm{<mo>=</mo>}\left(\begin{array}{cc}\cos \mathrm{<mo\; stretchy="false">(</mo>}\theta \mathrm{<mo\; stretchy="false">)</mo>}& -\sin \mathrm{<mo\; stretchy="false">(</mo>}\theta \mathrm{<mo\; stretchy="false">)</mo>}\\ \sin \mathrm{<mo\; stretchy="false">(</mo>}\theta \mathrm{<mo\; stretchy="false">)</mo>}& \cos \mathrm{<mo\; stretchy="false">(</mo>}\theta \mathrm{<mo\; stretchy="false">)</mo>}\end{array}\right)\mathrm{<mo>=</mo>}\left(\begin{array}{cc}C& -S\\ S& C\end{array}\right)$

With S ≠ 0 as the angle is different of 0[π]. The case θ = 0[π] is not meaningful, as Q = ± l₂.

From Lemma 2, we know that QN =NQ. Using the notations from (5), we have:

$Q\mathcal{N}\mathrm{<mo>=</mo>}\mathcal{N}Q\Leftarrow \{\begin{array}{cc}aC-bS& \mathrm{<mo>=</mo>}aC+bS\\ bC-cS& \mathrm{<mo>=</mo>}-aS+bC\end{array}$

$\Leftarrow \{\begin{array}{cc}bS& \mathrm{<mo>=</mo>0}\\ aS& \mathrm{<mo>=</mo>}cS\\ & \end{array}$

$\Leftarrow \{\begin{array}{cc}b& \mathrm{<mo>=</mo>0}\\ a& \mathrm{<mo>=</mo>}c\\ & \end{array}\text{as}S\ne 0$

So $\mathcal{N}\mathrm{<mo>=</mo>}a{I}_2$ .

Applications in 2D

Lemma 7 (Applications to regular polygons in 2D): For a regular n-gon in 2D with an edge length of h, the generic formula (3) holds and the covariance edge matrix is equal to:

$\mathcal{N}\mathrm{<mo>=</mo>}{h}^2\frac{n}{d}{I}_d\mathrm{<mo>=</mo>}{h}^2\frac{n}{2}{I}_2$

Proof. Using Lemma 6 with a rotation of angle ${\theta }_n\mathrm{<mo>=</mo>}\frac{2\pi }{n}$ we get N = al2. Besides, from (6) of Lemma 3, we have a regular polygon tr(N) = nh². Moreover, we know that tr(N) = 2a. We can conclude that $\mathcal{N}\mathrm{<mo>=</mo>}\frac{n}{2}{h}^2{I}_2$ .

Remark 3: Using the polar coordinates of the vertices a proof of Lemma 6 and 7 can be made using direct computations.

Properties in 3D: We are now working with polyhedrons in three dimensions (d = 3). With Lemma 1, N is symmetric and we will denote N as:

$\mathcal{N}\mathrm{<mo>=</mo>}\left(\begin{array}{ccc}a& b& c\\ b& d& e\\ c& e& f\end{array}\right)\mathrm{<mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}\left(\begin{array}{ccc}{e}_{i\mathrm{,1}}^2& e_{i\mathrm{,1}}{e}_{i\mathrm{,2}}& e_{i\mathrm{,1}}{e}_{i\mathrm{,3}}\\ e_{i\mathrm{,1}}{e}_{i\mathrm{,2}}& e_{i\mathrm{,2}}^2& e_{i\mathrm{,2}}{e}_{i\mathrm{,3}}\\ e_{i\mathrm{,1}}{e}_{i\mathrm{,3}}& e_{i\mathrm{,2}}{e}_{i\mathrm{,3}}& e_{i\mathrm{,3}}^2\\ & & \end{array}\right)\mathrm{.}\text{ (8)}$

Invariants in 3D: When using a matrix of size three, we have three invariants: determinant, trace, and α1 the coefficient of degree one in the characteristic polynomial of the matrix:

$P_{\mathcal{N}}\mathrm{<mo\; stretchy="false">(</mo>}\lambda \mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}-{\lambda }^3+tr\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}{\lambda }^2-{\alpha }_1\lambda +\text{det}\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>.}\text{ (9)}$

In Lemmas 8, 9, and 10 we compute these invariants.

Lemma 8 (Invariants in 3D: trace): As in 2D in Lemma 3 the trace gives the sum of the squared length of all edges:

$tr\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}\parallel e_i{\parallel }^2$

Proof.

$\begin{array}{ll}tr\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}\hfill & \mathrm{<mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}\mathrm{<mo\; stretchy="false">(</mo>}{e}_{i\mathrm{,1}}^2+e_{i\mathrm{,2}}^2+e_{i\mathrm{,3}}^2\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}\parallel e_i{\parallel }^2\hfill \\ \hfill & \mathrm{<mo>=</mo>}{\lambda }_1+{\lambda }_2+{\lambda }_3\hfill \end{array}$

Lemma 9 (Invariants in 3D: $_1$): Proof. Computations give the following formula for the invariant α1:

$\begin{array}{ll}{\alpha }_1\hfill & \mathrm{<mo>=</mo>}{\lambda }_1{\lambda }_2+{\lambda }_1{\lambda }_3+{\lambda }_2{\lambda }_3\hfill \\ \hfill & \mathrm{<mo>=</mo>}{\mathcal{N}}_{11}{\mathcal{N}}_{22}+{\mathcal{N}}_{11}{\mathcal{N}}_{33}+{\mathcal{N}}_{22}{\mathcal{N}}_{33}-{\mathcal{N}}_{12}^2-{\mathcal{N}}_{13}^2-{\mathcal{N}}_{23}^2\hfill \end{array}$

Remark 4: For a tetrahedron, computations done in Chapter One of [17] give:

${\alpha }_1\mathrm{<mo>=</mo>}{\displaystyle \sum _{f\mathrm{<mo>=</mo>0}}^{F-1}}\mathrm{<mo>|</mo>}{T}_f{\mathrm{<mo>|</mo>}}^2\text{ (10)}$

Where | T_f | is the area triangle face f.

Lemma 10 (Invariants in 3D: determinant): Proof. The determinant is:

$\begin{array}{ll}\text{det}\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}\hfill & \mathrm{<mo>=</mo>}{\mathcal{N}}_{11}{\mathcal{N}}_{22}{\mathcal{N}}_{33}+2{\mathcal{N}}_{12}{\mathcal{N}}_{13}{\mathcal{N}}_{23}\hfill \\ \hfill & -{\mathcal{N}}_{11}{\mathcal{N}}_{23}^2-{\mathcal{N}}_{22}{\mathcal{N}}_{13}^2-{\mathcal{N}}_{33}{\mathcal{N}}_{12}^2\hfill \\ \hfill & \mathrm{<mo>=</mo>}{\lambda }_1{\lambda }_2{\lambda }_3\hfill \end{array}$

Remark 5: Following the computations from [17,20] we have for a tetrahedron:

$\text{det}\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\left(\frac{d+1}{2}\right)}^d\frac{2^d{\mathrm{<mo\; stretchy="false">(</mo>}d\mathrm{<mo>!</mo><mo\; stretchy="false">)</mo>}}^2}{d+1}\mathrm{<mo>|</mo>}T{\mathrm{<mo>|</mo>}}^2\mathrm{<mo>=</mo>576<mo>|</mo>}T{\mathrm{<mo>|</mo>}}^2$

Where |T| is the volume of the tetrahedron.

Remark 6: It is more complex to extract geometric expressions of det(N) and 1 for other regular polyhedrons.

Invariances by isometric transformations in 3D: In the following lemmas, we show the form of the covariance edges matrix when the polyhedron is invariant by various isometric applications.

Lemma 11 (Effects of 3D axis reflections): Consider a polyhedron P in 3D. If this polyhedron is invariant by two reflections around planes then the covariance edges matrix is diagonal.

Proof. Let Q be the reflection around the plane z = 0:

$Q\mathrm{<mo>=</mo>}{Q}_{rz}\mathrm{<mo>=</mo>}\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& -1\end{array}\right)$

If the polyhedron is invariant by Q Lemma 2 holds and we have QN = NQ. This leads to:

$\mathcal{N}\mathrm{<mo>=</mo>}\left(\begin{array}{ccc}a& b& 0\\ b& d& 0\\ 0& 0& f\end{array}\right)$

In the case of the reflection around the plane y = 0 we have:

$\mathcal{N}\mathrm{<mo>=</mo>}\left(\begin{array}{ccc}a& 0& c\\ 0& d& 0\\ c& 0& f\end{array}\right)$

and for the plane x = 0:

$\mathcal{N}\mathrm{<mo>=</mo>}\left(\begin{array}{ccc}a& 0& 0\\ 0& d& e\\ 0& e& f\end{array}\right)$

If two of the three reflections let the polyhedron invariants, we can conclude that N is diagonal.

Lemma 12 (Effects of 3D axis rotations) Consider a polyhedron P in 3D. If this polyhedron is invariant by a rotation around one axis with an angle θ (θ ≠ 0[π]) then the covariance edges matrix is diagonal.

Proof. Let Q be the rotation matrix around the z-axis with θ angle:

$Q\mathrm{<mo>=</mo>}{R}_z\mathrm{<mo\; stretchy="false">(</mo>}\theta \mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\left(\begin{array}{ccc}\cos \mathrm{<mo\; stretchy="false">(</mo>}\theta \mathrm{<mo\; stretchy="false">)</mo>}& -\sin \mathrm{<mo\; stretchy="false">(</mo>}\theta \mathrm{<mo\; stretchy="false">)</mo>}& 0\\ \sin \mathrm{<mo\; stretchy="false">(</mo>}\theta \mathrm{<mo\; stretchy="false">)</mo>}& \cos \mathrm{<mo\; stretchy="false">(</mo>}\theta \mathrm{<mo\; stretchy="false">)</mo>}& 0\\ 0& 0& 1\end{array}\right)$

We avoid the case ∅ ≠ 0[π] in order to remove the case Q = 1 and the case of the reflections done previously in Lemma 11 as R_z(π) = -Q_rz.

In this case, if the polyhedron is invariants by Q, Lemma 2 holds and computations similar to the ones done in 2D (Lemma 6) of NQ = QN give:

$\mathcal{N}\mathrm{<mo>=</mo>}\left(\begin{array}{ccc}a& 0& 0\\ 0& a& 0\\ 0& 0& f\end{array}\right)$

With Q = R_y(∅)it leads to:

$\mathcal{N}\mathrm{<mo>=</mo>}\left(\begin{array}{ccc}a& 0& 0\\ 0& d& 0\\ 0& 0& a\end{array}\right)$

and for Q = R_x(∅)we have:

$\mathcal{N}\mathrm{<mo>=</mo>}\left(\begin{array}{ccc}a& 0& 0\\ 0& d& 0\\ 0& 0& d\end{array}\right)$

In all three cases, the covariance edges matrix is diagonal.

Lemma 13: Let P be a regular polyhedron with n edges with the length of h which is invariant by two rotations of angle different of 0[π] with two different axis. The generic formula (3) holds and the covariance edges matrix is equal to:

$\mathcal{N}\mathrm{<mo>=</mo>}{h}^2\frac{n}{d}{I}_d$

Proof: Let us build a basis by taking the two rotations axis and a third vector. On this basis, we can apply twice Lemma 12 to get a matrix proportional to the identity N = al3. Then using Lemma 8 and the computations of trace (8) we get tr(N) = 3a = nh². It leads to . $\mathcal{N}\mathrm{<mo>=</mo>}{h}^2\frac{n}{3}{I}_3$

Besides, as the covariance edges matrix is proportional to the identity it will be the same in all bases as stated in Remark 1.

Applications in 3D

Lemma 14 (Applications to tetrahedrons): For a regular tetrahedron with an edge length of h, the generic formula (3) holds and the covariance edge matrix is equal to:

$\mathcal{N}\mathrm{<mo>=</mo>}{h}^2\frac{n}{d}{I}_d\mathrm{<mo>=</mo>3}{h}^2{I}_3$

Proof: A regular tetrahedron is invariant by rotations of the angle $\frac{2\pi }{3}$ around the axis from one vertex to the center of the opposite face. Applying Lemma 13 gives the results.

Lemma 15 (Applications to cubes): For a regular cube with an edge length of h, the generic formula (3) holds and the covariance edge matrix is equal to:

$\mathcal{N}\mathrm{<mo>=</mo>}{h}^2\frac{n}{d}{I}_d\mathrm{<mo>=</mo>4}{h}^2{I}_3$

Proof: A cube is invariant by three rotations of angle $\frac{\pi }{2}$ with an axis going from the center of the current face to the opposite face. Lemma 13 holds and we get N = 4h^2l3.

Remark 7: The proof can also be done by considering the cube as a prism with a square basis (see Lemma 16).

Lemma 16 (Applications to prisms): For a regular m-prism with n = 3m edges of size h, the generic formula (3) holds and the covariance edge matrix is equal to:

$\mathcal{N}\mathrm{<mo>=</mo>}{h}^2\frac{n}{d}{I}_d$

Proof: Let be a basis with the two first vectors inside the plane of the m-gon. Let be the last vector orthogonal and going from the center of one polygon to the other. Along this last vector, a prism is invariant by a rotation of angle $\frac{2\pi }{m}$ , so Lemma 12 applies and we get:

$\mathcal{N}\mathrm{<mo>=</mo>}\left(\begin{array}{ccc}a& 0& 0\\ 0& a& 0\\ 0& 0& f\end{array}\right)$

Let v be one edge vector collinear to the rotation axis. We have Nv = fv. Besides:

$\mathcal{N}v\mathrm{<mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^n}\mathrm{<mo\; stretchy="false">(</mo>}{e}_i{e}_i^T\mathrm{<mo\; stretchy="false">)</mo>}v\mathrm{<mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^n}{e}_i\mathrm{<mo\; stretchy="false">(</mo>}{e}_i^{T}v\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^n}\mathrm{<mo\; stretchy="false">(</mo>}{e}_i^{T}v\mathrm{<mo\; stretchy="false">)</mo>}{e}_i\mathrm{<mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^n}\mathrm{<mo\; stretchy="false">(</mo>}{e}_i\cdot v\mathrm{<mo\; stretchy="false">)</mo>}{e}_i$

For all e_i in the two m-gons we have (ei. v) = 0. For the others, we have (ei. v)ei = h²v as all the vectors are collinear. This leads to Nv = mh²v. From Lemma 8 and the computations of the trace (8), we have that tr(N) = nh² = 3mh² and here we have tr(N) = 2a+f. Everything leads to:

$\{\begin{array}{cc}\mathcal{N}v& \mathrm{<mo>=</mo>}fv\mathrm{<mo>=</mo>}m{h}^{2}v\mathrm{<mo>=</mo>}\frac{n}{3}{h}^{2}v\\ tr\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}& \mathrm{<mo>=</mo>2}a+f\mathrm{<mo>=</mo>}n{h}^2\end{array}\Rightarrow a\mathrm{<mo>=</mo>}f\mathrm{<mo>=</mo>}\frac{n}{3}{h}^2\mathrm{.}$

We can conclude that $\mathcal{N}\mathrm{<mo>=</mo>}\frac{n}{3}{h}^2{I}_3$ . This result is valid on all basis as stated in Remark 1.

Lemma 17 (Applications to square pyramids): For a regular square pyramid with an edge length of h, the generic formula (3) does not apply as the covariance edges matrix is only diagonal on a specific basis. This basis is defined by taking the two first vectors in the plane of the square. The last vector is orthogonal to the two firsts and goes from the center of the square to the opposite vertex. On this basis, the covariance edges matrix is:

$\mathcal{N}\mathrm{<mo>=</mo>}{h}^2\left(\begin{array}{ccc}3& 0& 0\\ 0& 3& 0\\ 0& 0& 2\end{array}\right)$

Proof. In a basis where the last vector is going from the center of the square to the opposite vertex, Lemma 12 applies with an angle of $\frac{\pi }{2}$ and we get in this basis:

$\mathcal{N}\mathrm{<mo>=</mo>}\left(\begin{array}{ccc}a& 0& 0\\ 0& a& 0\\ 0& 0& f\end{array}\right)$

From Lemma 8 and the computations of the trace (8) we get:

$tr\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>2}a+f\mathrm{<mo>=</mo>}n{h}^2\mathrm{<mo>=</mo>8}{h}^2\mathrm{.}$

Let e0 be one side of the square as in Figure 2. We have:

$\mathcal{N}{e}_0\mathrm{<mo>=</mo>}\left(\begin{array}{c}a{e}_{\mathrm{0,}x}\\ a{e}_{\mathrm{0,}y}\\ 0\end{array}\right)\mathrm{<mo>=</mo>}a{e}_0\text{,as}{e}_{\mathrm{0,}z}\mathrm{<mo>=</mo>0}$

By recomputing directly this product, we get:

$\mathcal{N}{e}_0\mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}{e}_i{e}_i^T\mathrm{<mo\; stretchy="false">)</mo>}{e}_0$

$\mathrm{<mo>=</mo>}{\displaystyle \sum _{i\mathrm{<mo>=</mo>0}}^{n-1}}\mathrm{<mo\; stretchy="false">(</mo>}{e}_i^T{e}_0\mathrm{<mo\; stretchy="false">)</mo>}{e}_i$

$\mathrm{<mo>=</mo>}\underset{\text{square}}{\underbrace{\mathrm{<mo\; stretchy="false">(</mo>}{e}_0^T{e}_0\mathrm{<mo\; stretchy="false">)</mo>}{n}_0+\mathrm{<mo\; stretchy="false">(</mo>}{e}_1^T{e}_0\mathrm{<mo\; stretchy="false">)</mo>}{e}_1+\mathrm{<mo\; stretchy="false">(</mo>}{e}_2^T{e}_0\mathrm{<mo\; stretchy="false">)</mo>}{e}_2+\mathrm{<mo\; stretchy="false">(</mo>}{e}_3^T{e}_0\mathrm{<mo\; stretchy="false">)</mo>}{e}_3}}$

$+\underset{\text{triangles}}{\underbrace{\mathrm{<mo\; stretchy="false">(</mo>}{e}_4^T{e}_0\mathrm{<mo\; stretchy="false">)</mo>}{e}_4+\mathrm{<mo\; stretchy="false">(</mo>}{e}_5^T{e}_0\mathrm{<mo\; stretchy="false">)</mo>}{e}_5+\mathrm{<mo\; stretchy="false">(</mo>}{e}_6^T{e}_0\mathrm{<mo\; stretchy="false">)</mo>}{e}_6+\mathrm{<mo\; stretchy="false">(</mo>}{e}_7^T{e}_0\mathrm{<mo\; stretchy="false">)</mo>}{e}_7}}$

$\mathrm{<mo>=</mo>}{h}^2{e}_0+0+\mathrm{<mo\; stretchy="false">(</mo>}-h^2\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">(</mo>}{e}_2\mathrm{<mo\; stretchy="false">)</mo>}+0+0.5h^2{e}_4$

$-0.5h^2{e}_5-0.5h^2{e}_6+0.5h^2{e}_7$

$\mathrm{<mo>=</mo>}{h}^2\mathrm{<mo\; stretchy="false">(</mo>}{e}_0+0+e_0+0+\mathrm{0.5<mo\; stretchy="false">(</mo>}{e}_4-e_5\mathrm{<mo\; stretchy="false">)</mo>}+\mathrm{0.5<mo\; stretchy="false">(</mo>}{e}_7-e_6\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}$

$\mathrm{<mo>=</mo>}{h}^2\mathrm{<mo\; stretchy="false">(</mo>2}{e}_0+\mathrm{0.5<mo\; stretchy="false">(</mo>}{e}_0\mathrm{<mo\; stretchy="false">)</mo>}+\mathrm{0.5<mo\; stretchy="false">(</mo>}-e_2\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}$

$\mathrm{<mo>=</mo>}{h}^2\mathrm{<mo\; stretchy="false">(</mo>2}{e}_0+\mathrm{0.5<mo\; stretchy="false">(</mo>}{e}_0\mathrm{<mo\; stretchy="false">)</mo>}+\mathrm{0.5<mo\; stretchy="false">(</mo>}{e}_0\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}$

$\mathrm{<mo>=</mo>3}{h}^2{e}_0$

Everything leads to:

$\{\begin{array}{cc}tr\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}& \mathrm{<mo>=</mo>2}a+f\mathrm{<mo>=</mo>8}{h}^2\\ \mathcal{N}{e}_0& \mathrm{<mo>=</mo>}a{e}_0\mathrm{<mo>=</mo>3}{h}^2{e}_0\end{array}\Rightarrow \{\begin{array}{cc}f& \mathrm{<mo>=</mo>2}{h}^2\\ a& \mathrm{<mo>=</mo>3}{h}^2\end{array}$

e can conclude that for a regular square pyramid on a specific basis, we have:

$\mathcal{N}\mathrm{<mo>=</mo>}{h}^2\left(\begin{array}{ccc}3& 0& 0\\ 0& 3& 0\\ 0& 0& 2\end{array}\right)$

Remark 8: From Remark 1, we recall the fact that the covariance edges matrix for a pyramid is only diagonal in a basis composed of two vectors in the square, and the third vector is orthogonal to the two firsts and going from the center of the square to the opposite vertex.

Lemma 18 (Applications to octahedrons): For a regular octahedron with an edge length of h, the generic formula (3) holds and the covariance edge matrix is equal to:

$\mathcal{N}\mathrm{<mo>=</mo>}{h}^2\frac{n}{d}{I}_d\mathrm{<mo>=</mo>4}{h}^2{I}_3$

Proof. An octahedron is invariant by three rotations of angle $\frac{\pi }{2}$ :

1. one with the axis from the center of the square to the two vertices not belonging to the square
2. two with the axis joining two opposite vertices of the square.

Lemma 13 holds and we get N = 4h^2l3.

Lemma 19 (Applications to symmetrized pyramids): As a pyramidal element is not a regular polyhedron, we propose to complete this element by a symmetric part to obtain an octahedron. To this end, the opposite apex is the symmetrical point of the current apex with respect to the centroid of the opposite quadrilateral face. For the obtained octahedron one can apply Lemma 18 to get:

$\mathcal{N}\mathrm{<mo>=</mo>}{h}^2\frac{n}{d}{I}_d\mathrm{<mo>=</mo>4}{h}^2{I}_3$

Remark 9: The formula (3) is verified numerically for all five Platonic solids, all thirteen Archimedean solids, and some of the Johnson solids. It is not valid for anti-prisms (as for the square pyramid).

Shape quality using the covariance edges matrix

Shape quality measures: The covariance edges matrix N is proportional to the identity of regular elements which are isotropic. When moving to anisotropic elements, this matrix is no more proportional to the identity. One may use this property to define shape quality measures.

One of the possible shape quality measures of a polygon P is defined as:

$q_{\lambda }\mathrm{<mo\; stretchy="false">(</mo>}P\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\frac{{\lambda }_{\min }}{{\lambda }_{\max }}$

Where λ_min and λ_max are the smallest and greatest eigenvalues of the covariance edges matrix N. This ratio of the eigenvalues defines the anisotropy of the matrix.

If the computations of eigenvalues are too costly, one may use the ratio of the means of the eigenvalues as an alternative, as we can use the invariants of the matrix to define means. In 2D, the computations of the Arithmetic, Geometric, and Harmonic means of λ₁ and λ₂ give:

$\begin{array}{ll}A\hfill & \mathrm{<mo>=</mo>}\frac{{\lambda }_1+{\lambda }_2}{d}\mathrm{<mo>=</mo>}\frac{tr\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}}{d}\hfill \\ G\hfill & \mathrm{<mo>=</mo><mo\; stretchy="false">(</mo>}{\lambda }_1{\lambda }_2{\mathrm{<mo\; stretchy="false">)</mo>}}^{\mathrm{1<mo>/</mo>}d}\mathrm{<mo>=</mo>}\sqrt{\text{det}\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}}\hfill \\ H\hfill & \mathrm{<mo>=</mo>}\frac{d}{\frac{1}{{\lambda }_1}+\frac{1}{{\lambda }_2}}\mathrm{<mo>=</mo>}d\frac{{\lambda }_1{\lambda }_2}{{\lambda }_1+{\lambda }_2}\mathrm{<mo>=</mo>}d\frac{\text{det}\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}}{tr\mathrm{<mo\; stretchy="false">(</mo>}\mathcal{N}\mathrm{<mo\; stretchy="false">)</mo>}}\hfill \end{array}$

Let us recall, that these two eigenvalues are real and positive as the covariance edges matrix is symmetric positive-definite (Lemma 1). The means are then positive. Besides, let us notice that 0 < H ≤ G ≤ A. We can then, define qualities between 0 and 1 by computing the ratio of two means:

$q_{GA}\mathrm{<mo>=</mo>}\frac{G}{A}{q}_{HA}\mathrm{<mo>=</mo>}\frac{H}{A}{q}_{HG}\mathrm{<mo>=</mo>}\frac{H}{G}$

One can easily notice that qGA = qHG and that qHA = q2GA. Besides, for a triangle, these new qualities are equivalent to the mean ratio η (1) as we have:

$\begin{array}{ll}{q}_{GA}(T)=\sqrt{q_{HA}}(T)=q_{HG}(T)\hfill & =2\frac{\sqrt{det(N)}}{tr(N)}\hfill \\ \hfill & =2\frac{\sqrt{3{(2|T|)}^2}}{{\displaystyle \sum _{i=0}^{n-1}}P{e}_i{P}^2}\hfill \\ \hfill & =4\sqrt{3}\frac{\left|T\right|}{{\displaystyle \sum _{i=0}^2}P{e}_i{P}^2}\hfill \\ \hfill & =\eta (T)\hfill \end{array}$

Extension of the quality for degenerated elements

In the case of a degenerated quadrilateral:

$O\mathrm{<mo>=</mo>}\left(\begin{array}{c}0\\ 0\end{array}\right)A\mathrm{<mo>=</mo>}\left(\begin{array}{c}1\\ 0\end{array}\right)B\mathrm{<mo>=</mo>}\left(\begin{array}{c}0\\ 0\end{array}\right)C\mathrm{<mo>=</mo>}\left(\begin{array}{c}0\\ 1\end{array}\right)$

the covariance edges matrix is:

$\mathcal{N}\mathrm{<mo>=</mo>}\left(\begin{array}{cc}2& 0\\ 0& 2\\ & \end{array}\right)$

Which gives, qλ = qGA = 1 which is not satisfactory as we want to avoid such elements. To overcome this difficulty, we introduce the jacobian of the elements in the quality, for instance:

$q_{J\lambda }\mathrm{<mo\; stretchy="false">(</mo>}P\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}{\left(\frac{J_{\min }}{J_{\max }}\right)}^{\alpha }{\left(\frac{{\lambda }_{\min }}{{\lambda }_{\max }}\right)}^{1-\alpha }\text{ (11)}$

where α is a parameter to give more or less influence to the Jacobian and J_min (J_max) is the minimal (maximal) value of the Jacobian over the elements. In the next sections, we set α = 1/3.

Applications on triangles: In the spirit of [11] we computed in Figure 3 the qualities of triangles ABC defined as:

$A\mathrm{<mo>=</mo>}\left(\begin{array}{c}-\mathrm{1<mo>/</mo>2}\\ 0\end{array}\right)B\mathrm{<mo>=</mo>}\left(\begin{array}{c}x\\ y\end{array}\right)C\mathrm{<mo>=</mo>}\left(\begin{array}{c}0\\ \mathrm{1<mo>/</mo>2}\end{array}\right)$

For each point, B(x,y) we compute the quality of the resulting triangle. In the case of triangles, the value of $\frac{J_{\min }}{J_{\max }}$ in (11) is equal to one. The results show a behaviour similar to the mean ratio (1)

Applications on quadrilaterals: Using the same idea for quadrilaterals, we computed in Figures 4,5 the qualities of various quadrilaterals. For the quadrilaterals, the ratio $\frac{J_{\min }}{J_{\max }}$ of (11) is computed using the minimal and maximal values of four determinants [21]:

$\left|\begin{array}{cc}OA& OC\end{array}\right|\left|\begin{array}{cc}OA& AB\end{array}\right|\left|\begin{array}{cc}CB& OC\end{array}\right|\left|\begin{array}{cc}CB& AB\end{array}\right|$

The comparison is made between q_jλ (11) and the quality defined as:

$q\mathrm{<mo\; stretchy="false">(</mo>}Q\mathrm{<mo\; stretchy="false">)</mo><mo>=</mo>}\underset{i\in \mathrm{<mo\; stretchy="false">[</mo>1<mo>;</mo>4<mo\; stretchy="false">]</mo>}}{{\displaystyle \min }}\mathrm{<mo\; stretchy="false">(</mo>}\eta \mathrm{<mo\; stretchy="false">(</mo>}{T}_i\mathrm{<mo\; stretchy="false">)</mo><mo\; stretchy="false">)</mo>}\text{ (12)}$

where the T_i is one of the four possible triangles made in a quadrilateral Q when cutting it into two triangles.

Figure 4 is obtained for several quadrilaterals OABC defined as:

$O\mathrm{<mo>=</mo>}\left(\begin{array}{c}0\\ 0\end{array}\right)A\mathrm{<mo>=</mo>}\left(\begin{array}{c}1\\ 0\end{array}\right)B\mathrm{<mo>=</mo>}\left(\begin{array}{c}x\\ y\end{array}\right)C\mathrm{<mo>=</mo>}\left(\begin{array}{c}0\\ 1\end{array}\right)$

In this case, the element with the greatest quality is the unit square S according to both qualities as q_jλ (S) = q(S) = 1.

Figure 5 is obtained for several quadrilaterals OABC defined as:

$O\mathrm{<mo>=</mo>}\left(\begin{array}{c}0\\ 0\end{array}\right)A\mathrm{<mo>=</mo>}\left(\begin{array}{c}2\\ 0\end{array}\right)B\mathrm{<mo>=</mo>}\left(\begin{array}{c}x\\ y\end{array}\right)C\mathrm{<mo>=</mo>}\left(\begin{array}{c}0\\ 1\end{array}\right)$

In this second case, the two qualities differ. In Figure 6, the elements with better quality are presented. q_jλ tends to have the best element for (x,y) = (1.35,2.05) with a quality near 0.67 whereas when splitting into two triangles (12) it gives a maximum for (x,y) = (1,2) with a quality of 0.8. The choice of q_jλ may be better as the element is more isotropic (the ratio of the minimal length over the maximal length of edges is greater). Besides, only on global maximum is found whereas when splitting into triangles there is a zone where all the quadrilaterals have a quality near 0.8 which is not convenient to do optimisation on shape quality measure.

Conclusion

A new algebraic shape quality measure for polygons and polyhedrons is introduced. This measure depends only on the covariance edges matrix, namely the ratio between the smallest and the greatest corresponding eigenvalues. Using the invariants of this matrix, several alternative shape quality measures are also proposed. In particular, one of the proposed measures, applied to simplicial elements, coincides with a known geometric measure. Hence, this measure can be seen as a generalisation to other elements. The novelty of this measure is its generality: in this work, it is applied only to triangles and quadrilaterals but future developments will focus on 3D applications. The application to mesh optimisation is the next step and the main advantage of this new measure is the fact that it is the same expression for all elements.

As shown in [17] and recalled in Section 3.2, the covariance edges matrix is related to the metric of the element for the simplicial element. It is interesting to investigate the generalisation of the metric element for non-simplicial elements based on the covariance edge matrix.

The extension of the covariance edges matrix to high-order elements may require more investigation, in particular, the element edges are curved, and differential geometric must be taken into account.

1. Shewchuk JR. What is a Good Linear Element? - Interpolation, Conditioning, and Quality Measures. In: In 11th International Meshing Roundtable. 2002; 115-26.
2. Knupp P. Remarks on Mesh Quality. 46th AIAA Aerospace Sciences Meeting and Exhibit. 2007; 12.
3. George PL, Borouchaki H. Delaunay triangulation and meshing. Application to finite elements. Paris: Edition Herm`es; 1998.
4. Frey PJ, George PL. Mesh generation. Application to finite elements. Oxford: Hermes Science Publishing. 2000.
5. Liu A, Joe B. Relationship between tetrahedron shape measures. BIT. 1994 Jun; 34(2):268-87.
6. Parthasarathy VN, Graichen CM, Hathaway AF. A comparison of tetrahedron quality measures. Finite Elements in Analysis and Design. 1994; 15(3):255-61.
7. Dompierre J, Labb´e P, Guibault F, Camarero R. Proposal of Benchmarks for 3D Unstructured Tetrahedral Mesh Optimization. In: Proceedings of the 7th International Meshing RoundTable’98. 1998; 459-78.
8. Field DA. Qualitative measures for initial meshes. International Journal for Numerical Methods in Engineering. 2000 Feb; 47(4):887- 906.
9. Knupp PM. Algebraic mesh quality metrics. SIAM J Sci Comput. 2001; 23(1):193-218. 18
10. Pebay PP, Baker TJ. Analysis of triangle quality measures. Mathematics of Computation. 2003 jan; 72(244):1817-40.
11. Dompierre J, Vallet MG, Labb´e P, Guibault F. An analysis of simplex shape measures for anisotropic meshes. Computer Methods in Applied Mechanics and Engineering. 2005; 194(48):4895-914. Unstructured Mesh Generation.
12. Farin G. Shape Measures for Triangles. IEEE Trans Vis Comput Graph. 2012 Jan;18(1):43-6. doi: 10.1109/TVCG.2010.256. Epub 2010 Dec 17. PMID: 21149882.
13. Knupp P, Ernst C, Thompson D, Stimpson C, Pebay P. The verdict geometric quality library. 2006.
14. Caendish JC, Field DA, Frey WH. An apporach to automatic threedimensional finite element mesh generation. International Journal for Numerical Methods in Engineering. 1985 feb; 21(2):329-47.
15. Munson T. Mesh shape-quality optimization using the inverse meanratio metric. Mathematical Programming. 2006 Aug; 110(3):561-90.
16. Bhatia RP, Lawrence KL. Two-dimensional finite element mesh generation based on stripwise automatic triangulation. Computers and Structures. 1990; 36(2):309-19.
17. George PL, Borouchaki H, Alauzet F, Laug P, Loseille A, Marechal L. Meshing, Geometric Modeling and Numerical Simulation 2. John Wiley & Sons, Ltd. 2019.
18. Liu A, Joe B. On the shape of tetrahedra from bisection. Mathematics of Computation. 1994; 63(207):141-54.
19. Lo SH. Optimization of tetrahedral meshes based on element shape measures. Computers and Structures. 1997 Jun; 63(5):951-61.
20. George PL, Borouchaki H. M´etrique et qualite dun simplexe. C R, Math, Acad Sci Paris. 2017; 355(1):105-12.
21. Borouchaki H, George PL. Meshing, Geometric Modeling and Numerical Simulation 1. John Wiley & Sons, Inc. 2017.