@why-math 2015-01-23T07:40:32.000000Z 字数 10631 阅读 843

最优单元角度算法研究

网格

一, 四边形网格

给定一个由

$N$ 个节点 $\{V_i\}_{i=1}^N$ 和
$NT$ 个单元 $\{\tau_i :=(V_k,V_j, V_m, V_n) | V_k, V_j, V_m, V_n \in V \}_{i=1}^{NT}$

组成的四边形网格 $\mathcal T$ .

假设:

每个单元的四个顶点按逆时针方向排列
$\mathcal T$ 是一个连通图

问题:

每个单元的四个顶点对应的角度为多少时, 四边形网格

T $\mathcal T$ 的单元形状最接近正方形?

设 $A_1, A_2, A_3, A_4$ 是四个长度为 $NT$ 的列向量, 其中 $A_i$ 的第 $j$ 个分量为第 $j$ 个单元第 $i$ 个顶点对应的角度值.

设 $I_1, I_2, I_3, I_4$ 是四个长度为 $NT$ 的列向量, 其中 $I_i$ 的第 $j$ 个分量为第 $j$ 个单元的第 $i$ 个顶点对应的理想角度值.

建立如下极小化模型:

min \sum i = 1 4 (A i - I i) T (A i - I i)

$\min \sum\limits_{i=1}^4 (A_i - I_i)^T(A_i - I_i)$

其中 $A_i, i=1,2,3,4,$ 满足如下条件:

(E N T E N T E N T E N T) ⎛ ⎝ ⎜ ⎜ ⎜ A 1 A 2 A 3 A 4 ⎞ ⎠ ⎟ ⎟ ⎟ (C 1 N \times N T C 2 N \times N T C 3 N \times N T C 4 N \times N T) ⎛ ⎝ ⎜ ⎜ ⎜ A 1 A 2 A 3 A 4 ⎞ ⎠ ⎟ ⎟ ⎟ = = B M

$\begin{aligned} \begin{pmatrix} E_{NT} & E_{NT} & E_{NT} & E_{NT} \end{pmatrix} \begin{pmatrix} A_1 \\ A_2 \\ A_3 \\A_4 \end{pmatrix} & = & B \\ \begin{pmatrix} C^1_{N\times NT} & C^2_{N\times NT} & C^3_{N\times NT} & C^4_{N\times NT} \end{pmatrix} \begin{pmatrix} A_1 \\ A_2 \\ A_3 \\A_4 \end{pmatrix} & = & M \end{aligned}$

其中

$E_{NT}:$ $NT$ 阶单位矩阵;
$C_{N\times NT}^k:$
$C k N \times N T (i, j) = {1, 0, 第 i 个节点是第 j 个单元的第 k 个顶点, 其它;$ $C^k_{N\times NT}(i,j) = \begin{cases} 1, & \mbox{第 }i\mbox{ 个节点是第 }j\mbox{ 个单元的第 }k\mbox{ 个顶点,} \\ 0, & \mbox{其它;} \end{cases}$
$C^k_{N\times NT}$ 的每一列有且只有一个1, 其余全为0.
$B:$ 长度为 $NT$ 的列向量, $B(i)$ 为第 $i$ 个单元四个角的内角和, 这里都为360度;
$M:$ 长度为 $N$ 的列向量, $M(i)$ 为第 $i$ 个节点周围的角度和.

引入拉格郞日乘子 $\Lambda_1, \Lambda_2$ , 构造如下拉格郞日函数:

= F (A 1, A 2, A 3, A 4, Λ 1, Λ 2) \sum i = 1 4 (A i - I i) T (A i - I i) + Λ T 1 {(E N T E N T E N T E N T) ⎛ ⎝ ⎜ ⎜ ⎜ A 1 A 2 A 3 A 4 ⎞ ⎠ ⎟ ⎟ ⎟ - B} + Λ 2 {(C 1 N \times N T C 2 N \times N T C 3 N \times N T C 4 N \times N T) ⎛ ⎝ ⎜ ⎜ ⎜ A 1 A 2 A 3 A 4 ⎞ ⎠ ⎟ ⎟ ⎟ - M}

$\begin{aligned} &F(A_1,A_2,A_3,A_4,\Lambda_1,\Lambda_2) \\ =&\sum\limits_{i=1}^4 (A_i - I_i)^T(A_i - I_i) \\ &+ \Lambda_1^T \{\begin{pmatrix} E_{NT} & E_{NT} & E_{NT} & E_{NT} \end{pmatrix} \begin{pmatrix} A_1 \\ A_2 \\ A_3 \\A_4 \end{pmatrix} - B\} \\ & + \Lambda_2\{\begin{pmatrix} C^1_{N\times NT} & C^2_{N\times NT} & C^3_{N\times NT} & C^4_{N\times NT} \end{pmatrix} \begin{pmatrix} A_1 \\ A_2 \\ A_3 \\A_4 \end{pmatrix} - M\} \end{aligned}$

求 $F(A_1,A_2,A_3,A_4,\Lambda_1,\Lambda_2)$ 的驻点, 可得如下方程:

⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ 2 E N T 000 E N T C 1 N \times N T 0 2 E N T 00 E N T C 2 N \times N T 00 2 E N T 0 E N T C 3 N \times N T 000 2 E N T E N T C 4 N \times N T E N T E N T E N T E N T 00 (C 1 N \times N T) T (C 2 N \times N T) T (C 3 N \times N T) T (C 4 N \times N T) T 00 ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ A 1 A 2 A 2 A 3 Λ 1 Λ 2 ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ = ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ 2 I 1 2 I 2 2 I 3 2 I 4 B M ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟

$\begin{equation} \begin{pmatrix} 2E_{NT} & 0 & 0 & 0 & E_{NT} & (C_{N\times NT}^1)^T \\ 0 & 2E_{NT} & 0 & 0 & E_{NT} & (C_{N\times NT}^2)^T\\ 0 & 0 & 2E_{NT} & 0 & E_{NT} & (C_{N\times NT}^3)^T \\ 0 & 0 & 0 & 2E_{NT} & E_{NT} & (C_{N\times NT}^4)^T \\ E_{NT} & E_{NT} & E_{NT} & E_{NT}& 0 & 0 \\ C^1_{N\times NT} & C^2_{N\times NT} & C^3_{N\times NT} & C^4_{N\times NT} & 0 & 0 \end{pmatrix} \begin{pmatrix} A_1 \\ A_2 \\ A_2 \\ A_3 \\ \Lambda_1 \\ \Lambda_2 \end{pmatrix} = \begin{pmatrix} 2I_1 \\ 2I_2 \\ 2I_3 \\ 2I_4 \\ B \\M \end{pmatrix} \end{equation}$

下面用块消元法，化简上述代数系统的增广矩阵.

⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ 2 E N T 0000 C 1 N \times N T 0 2 E N T 000 C 2 N \times N T 00 2 E N T 00 C 3 N \times N T 000 2 E N T 0 C 4 N \times N T E N T E N T E N T E N T - 2 E N T 0 (C 1 N \times N T) T (C 2 N \times N T) T (C 3 N \times N T) T (C 4 N \times N T) T - 1 2 (\sum k = 1 4 C k N \times N T) T 0 2 I 1 2 I 2 2 I 3 2 I 4 B - \sum k = 1 4 I k M ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟

$\begin{pmatrix} 2E_{NT} & 0 & 0 & 0 & E_{NT} & (C_{N\times NT}^1)^T & 2I_1\\ 0 & 2E_{NT} & 0 & 0 & E_{NT} & (C_{N\times NT}^2)^T & 2I_2\\ 0 & 0 & 2E_{NT} & 0 & E_{NT} & (C_{N\times NT}^3)^T & 2I_3\\ 0 & 0 & 0 & 2E_{NT} & E_{NT} & (C_{N\times NT}^4)^T & 2I_4\\ 0 & 0 & 0 & 0 & -2E_{NT} & -\frac{1}{2} \left(\sum_{k=1}^4C_{N\times NT}^k \right)^T & B - \sum_{k=1}^4I_k\\ C^1_{N\times NT} & C^2_{N\times NT} & C^3_{N\times NT} & C^4_{N\times NT} & 0 & 0 & M \end{pmatrix}$

⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ E N T 00000 0 E N T 0000 00 E N T 000 000 E N T 00 1 2 E N T 1 2 E N T 1 2 E N T 1 2 E N T E N T - 1 2 \sum i = 1 4 C i N \times N T 1 2 (C 1 N \times N T) T 1 2 (C 2 N \times N T) T 1 2 (C 3 N \times N T) T 1 2 (C 4 N \times N T) T 1 4 (\sum k = 1 4 C k N \times N T) T - 1 2 \sum k = 1 4 C k N \times N T (C k N \times N T) T I 1 I 2 I 3 I 4 1 2 (\sum k = 1 4 I k - B) M - \sum k = 1 4 C k N \times N T I k ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟

$\begin{pmatrix} E_{NT} & 0 & 0 & 0 & \frac{1}{2}E_{NT} & \frac{1}{2}(C_{N\times NT}^1)^T & I_1\\ 0 & E_{NT} & 0 & 0 & \frac{1}{2}E_{NT} & \frac{1}{2}(C_{N\times NT}^2)^T & I_2\\ 0 & 0 & E_{NT} & 0 & \frac{1}{2}E_{NT} & \frac{1}{2}(C_{N\times NT}^3)^T & I _3\\ 0 & 0 & 0 & E_{NT} & \frac{1}{2}E_{NT} & \frac{1}{2}(C_{N\times NT}^4)^T & I_4\\ 0 & 0 & 0 & 0 & E_{NT} & \frac{1}{4} \left(\sum_{k=1}^4C_{N\times NT}^k \right)^T & \frac{1}{2}\left(\sum_{k=1}^4I_k-B\right)\\ 0& 0& 0& 0 & -\frac{1}{2} \sum_{i=1}^4C_{N\times NT}^i & -\frac{1}{2}\sum_{k=1}^4C_{N\times NT}^k(C_{N\times NT}^k)^T & M-\sum_{k=1}^4C_{N\times NT}^kI_k \end{pmatrix}$

⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ E N T 00000 0 E N T 0000 00 E N T 000 000 E N T 00 1 2 E N T 1 2 E N T 1 2 E N T 1 2 E N T E N T 0 1 2 (C 1 N \times N T) T 1 2 (C 2 N \times N T) T 1 2 (C 3 N \times N T) T 1 2 (C 4 N \times N T) T 1 4 (\sum k = 1 4 C k N \times N T) T G I 1 I 2 I 3 I 4 1 2 (\sum k = 1 4 I k - B) J ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟

$\begin{pmatrix} E_{NT} & 0 & 0 & 0 & \frac{1}{2}E_{NT} & \frac{1}{2}(C_{N\times NT}^1)^T & I_1\\ 0 & E_{NT} & 0 & 0 & \frac{1}{2}E_{NT} & \frac{1}{2}(C_{N\times NT}^2)^T & I_2\\ 0 & 0 & E_{NT} & 0 & \frac{1}{2}E_{NT} & \frac{1}{2}(C_{N\times NT}^3)^T & I_3\\ 0 & 0 & 0 & E_{NT} & \frac{1}{2}E_{NT} & \frac{1}{2}(C_{N\times NT}^4)^T & I_4\\ 0 & 0 & 0 & 0 & E_{NT} & \frac{1}{4} \left(\sum_{k=1}^4C_{N\times NT}^k \right)^T & \frac{1}{2}\left(\sum_{k=1}^4I_k - B\right)\\ 0& 0& 0& 0 & 0 & G & J \end{pmatrix}$

其中

G J = (\sum k = 1 4 C k N \times N T) (\sum k = 1 4 C k N \times N T) T - 4 \sum k = 1 4 C k N \times N T (C k N \times N T) T = 8 (M - \sum k = 1 4 C k N \times N T I k) + 2 (\sum k = 1 4 I k - B)

$\begin{aligned} G &= \left(\sum_{k=1}^4C_{N\times NT}^k\right)\left(\sum_{k=1}^4C_{N\times NT}^k \right)^T -4\sum_{k=1}^4C_{N\times NT}^k(C_{N\times NT}^k)^T\\ J &= 8(M-\sum_{k=1}^4C_{N\times NT}^kI_k)+2\left(\sum_{k=1}^4I_k - B\right) \end{aligned}$

其中， $\sum_{k=1}^4C_{N\times NT}^kI_k$ 表示每个节点处的理想角度之和，它和 $M$ 相等，所以

J = 2 (\sum k = 1 4 I k - B)

$J = 2\left(\sum_{k=1}^4I_k-B\right)$

下面分析 $G$ , 因为两个不同的节点不可能是同一个单元的第 $k$ 个顶点的，所以 $C_{N\times NT}^k$ 任意两行正交，则

D k = C k N \times N T (C k N \times N T) T

$D_k = C_{N\times NT}^k(C_{N\times NT}^k)^T$

是一个对角矩阵， $D_k(i,i)$ 是第 $k$ 个顶点为第 $i$ 个节点的单元的个数，可得对角矩阵

D = \sum k = 1 4 D k

$D = \sum_{k=1}^4 D_k$

其中 $D(i,i)$ 为第 $i$ 个节点的邻接单元个数。

记 $P = \sum_{k=1}^4 C_{N\times NT}^k$ , 则

P (i, j) = {1, 第 i 个 节 点 是 第 j 个 单 元 的 顶 点; 0, 否 则 .

$\begin{equation} P(i,j)= \begin{cases} 1, \text{ 第 }i\text{ 个节点是第 }j\text{个单元的顶点};\\ 0, \text{否则}. \end{cases} \end{equation}$

所以 $P$ 为节点和单元的邻接矩阵. 记 $Q = PP^T$ ，则

Q (i, j) = ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ 邻 接 单 元 的 个 数, i = j; 2, (i, j) 是 一 条 内 部 边; 1, i 和 j 在 同 一 个 单 元 内 但 不 相 邻 或 者 (i, j) 是 一 条 边 界 边; 0, 其 它 .

$\begin{equation} Q(i,j) = \begin{cases} \text{邻接单元的个数}, i=j;\\ 2, (i,j)\text{ 是一条内部边};\\ 1, i\text{ 和 }j\text{ 在同一个单元内但不相邻或者 }(i,j)\text{ 是一条边界边};\\ 0, \text{ 其它}. \end{cases} \end{equation}$

则 $-G = 4D - Q$ ，是四边形网格的 Laplacian 矩阵. 从图的理论出发，假设我们的网格为连通图，那么 $G$ 有且只有一个 0 特征值。

由以上分析，可得如下结论：
1. 矩阵 $A$ 的秩为 $6NT+N-1$ .
2. 只需求解一个 $N\times N$ 问题，即可快速求解该离散系统。

二, 三角形网格

给定一个由

$N$ 个节点 $\{V_i\}_{i=1}^N$ 和
$NT$ 个单元 $\{\tau_i :=(V_k, V_j, V_m) | V_k, V_j, V_m \in V \}_{i=1}^{NT}$

组成的三角形形网格 $\mathcal T$ .

设 $A_1, A_2, A_3$ 是三个个长度为 $NT$ 的列向量, 其中 $A_i$ 的第 $j$ 个分量为第 $j$ 个单元第 $i$ 个顶点对应的角度值.

设 $I_1, I_2, I_3$ 是三个长度为 $NT$ 的列向量, 其中 $I_i$ 的第 $j$ 个分量为第 $j$ 个单元的第 $i$ 个顶点对应的理想角度值.

建立如下极小化模型:

min \sum i = 1 3 (A i - I i) T (A i - I i)

$\min \sum\limits_{i=1}^3 (A_i - I_i)^T(A_i - I_i)$

其中 $A_i, i=1,2,3,$ 满足如下条件:

(E N T E N T E N T) ⎛ ⎝ A 1 A 2 A 3 ⎞ ⎠ (C 1 N \times N T C 2 N \times N T C 3 N \times N T) ⎛ ⎝ A 1 A 2 A 3 ⎞ ⎠ = = B M

$\begin{aligned} \begin{pmatrix} E_{NT} & E_{NT} & E_{NT} \end{pmatrix} \begin{pmatrix} A_1 \\ A_2 \\ A_3 \end{pmatrix} & = & B \\ \begin{pmatrix} C^1_{N\times NT} & C^2_{N\times NT} & C^3_{N\times NT} \end{pmatrix} \begin{pmatrix} A_1 \\ A_2 \\ A_3 \end{pmatrix} & = & M \end{aligned}$

其中

$E_{NT}:$ $NT$ 阶单位矩阵;
$C_{N\times NT}^k:$
$C k N \times N T (i, j) = {1, 0, 第 i 个节点是第 j 个单元的第 k 个顶点, 其它;$ $C^k_{N\times NT}(i,j) = \begin{cases} 1, & \mbox{第 }i\mbox{ 个节点是第 }j\mbox{ 个单元的第 }k\mbox{ 个顶点,} \\ 0, & \mbox{其它;} \end{cases}$
$C^k_{N\times NT}$ 的每一列有且只有一个1, 其余全为0.
$B:$ 长度为 $NT$ 的列向量, $B(i)$ 为第 $i$ 个三角形单元三个角的内角和, 这里都为360度;
$M:$ 长度为 $N$ 的列向量, $M(i)$ 为第 $i$ 个节点周围的角度和.

引入拉格郞日乘子 $\Lambda_1, \Lambda_2$ , 构造如下拉格郞日函数:

= F (A 1, A 2, A 3, Λ 1, Λ 2) \sum i = 1 3 (A i - I i) T (A i - I i) + Λ T 1 {(E N T E N T E N T) ⎛ ⎝ A 1 A 2 A 3 ⎞ ⎠ - B} + Λ 2 {(C 1 N \times N T C 2 N \times N T C 3 N \times N T) ⎛ ⎝ A 1 A 2 A 3 ⎞ ⎠ - M}

$\begin{aligned} &F(A_1,A_2,A_3,\Lambda_1,\Lambda_2) \\ =&\sum\limits_{i=1}^3 (A_i - I_i)^T(A_i - I_i) \\ &+ \Lambda_1^T \{\begin{pmatrix} E_{NT} & E_{NT} & E_{NT} \end{pmatrix} \begin{pmatrix} A_1 \\ A_2 \\ A_3 \end{pmatrix} - B\} \\ & + \Lambda_2\{\begin{pmatrix} C^1_{N\times NT} & C^2_{N\times NT} & C^3_{N\times NT} \end{pmatrix} \begin{pmatrix} A_1 \\ A_2 \\ A_3 \end{pmatrix} - M\} \end{aligned}$

求 $F(A_1,A_2,A_3，\Lambda_1,\Lambda_2)$ 的驻点, 可得如下方程:

⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ 2 E N T 00 E N T C 1 N \times N T 0 2 E N T 0 E N T C 2 N \times N T 00 2 E N T E N T C 3 N \times N T E N T E N T E N T 00 (C 1 N \times N T) T (C 2 N \times N T) T (C 3 N \times N T) T 00 ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ A 1 A 2 A 3 Λ 1 Λ 2 ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ = ⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ 2 I 1 2 I 2 2 I 3 B M ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟

$\begin{equation} \begin{pmatrix} 2E_{NT} & 0 & 0 & E_{NT} & (C_{N\times NT}^1)^T \\ 0 & 2E_{NT} & 0 & E_{NT} & (C_{N\times NT}^2)^T\\ 0 & 0 & 2E_{NT} & E_{NT} & (C_{N\times NT}^3)^T \\ E_{NT} & E_{NT} & E_{NT} & 0 & 0 \\ C^1_{N\times NT} & C^2_{N\times NT} & C^3_{N\times NT} & 0 & 0 \end{pmatrix} \begin{pmatrix} A_1 \\ A_2 \\ A_3 \\ \Lambda_1 \\ \Lambda_2 \end{pmatrix} = \begin{pmatrix} 2I_1 \\ 2I_2 \\ 2I_3 \\ B \\M \end{pmatrix} \end{equation}$

下面用块消元法，化简上述代数系统的增广矩阵.

⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ 2 E N T 000 C 1 N \times N T 0 2 E N T 00 C 2 N \times N T 00 2 E N T 0 C 3 N \times N T E N T E N T E N T - 3 2 E N T 0 (C 1 N \times N T) T (C 2 N \times N T) T (C 3 N \times N T) T - 1 2 (\sum k = 1 3 C k N \times N T) T 0 2 I 1 2 I 2 2 I 3 B - \sum k = 1 3 I k M ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟

$\begin{pmatrix} 2E_{NT} & 0 & 0 & E_{NT} & (C_{N\times NT}^1)^T & 2I_1\\ 0 & 2E_{NT} & 0 & E_{NT} & (C_{N\times NT}^2)^T & 2I_2\\ 0 & 0 & 2E_{NT} & E_{NT} & (C_{N\times NT}^3)^T & 2I_3\\ 0 & 0 & 0 & -\frac{3}{2}E_{NT} & -\frac{1}{2} \left(\sum_{k=1}^3C_{N\times NT}^k \right)^T & B - \sum_{k=1}^3I_k\\ C^1_{N\times NT} & C^2_{N\times NT} & C^3_{N\times NT} & 0 & 0 & M \end{pmatrix}$

⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ E N T 0000 0 E N T 000 00 E N T 00 1 2 E N T 1 2 E N T 1 2 E N T E N T - 1 2 \sum i = 1 3 C i N \times N T 1 2 (C 1 N \times N T) T 1 2 (C 2 N \times N T) T 1 2 (C 3 N \times N T) T 1 3 (\sum k = 1 3 C k N \times N T) T - 1 2 \sum k = 1 3 C k N \times N T (C k N \times N T) T I 1 I 2 I 3 2 3 (\sum k = 1 3 I k - B) M - \sum k = 1 3 C k N \times N T I k ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟

$\begin{pmatrix} E_{NT} & 0 & 0 & \frac{1}{2}E_{NT} & \frac{1}{2}(C_{N\times NT}^1)^T & I_1\\ 0 & E_{NT} & 0 & \frac{1}{2}E_{NT} & \frac{1}{2}(C_{N\times NT}^2)^T & I_2\\ 0 & 0 & E_{NT} & \frac{1}{2}E_{NT} & \frac{1}{2}(C_{N\times NT}^3)^T & I _3\\ 0 & 0 & 0 & E_{NT} & \frac{1}{3}\left(\sum_{k=1}^3C_{N\times NT}^k \right)^T & \frac{2}{3}\left( \sum_{k=1}^3I_k-B\right)\\ 0& 0& 0& -\frac{1}{2} \sum_{i=1}^3C_{N\times NT}^i & -\frac{1}{2}\sum_{k=1}^3C_{N\times NT}^k(C_{N\times NT}^k)^T & M-\sum_{k=1}^3C_{N\times NT}^kI_k \end{pmatrix}$

⎛ ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ E N T 0000 0 E N T 000 00 E N T 00 1 2 E N T 1 2 E N T 1 2 E N T E N T 0 1 2 (C 1 N \times N T) T 1 2 (C 2 N \times N T) T 1 2 (C 3 N \times N T) T 1 3 (\sum k = 1 3 C k N \times N T) T G I 1 I 2 I 3 2 3 (\sum k = 1 3 I k - B) J ⎞ ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟

其中

G J = (\sum k = 1 3 C k N \times N T) (\sum k = 1 3 C k N \times N T) T - 3 \sum k = 1 4 C k N \times N T (C k N \times N T) T = 6 (M - \sum k = 1 3 C k N \times N T I k) + 2 (\sum k = 1 3 I k - B)

$\begin{aligned} G &= \left(\sum_{k=1}^3C_{N\times NT}^k\right)\left(\sum_{k=1}^3C_{N\times NT}^k \right)^T -3\sum_{k=1}^4C_{N\times NT}^k(C_{N\times NT}^k)^T\\ J &= 6(M-\sum_{k=1}^3C_{N\times NT}^kI_k)+2\left(\sum_{k=1}^3I_k-B\right) \end{aligned}$

其中， $\sum_{k=1}^3C_{N\times NT}^kI_k$ 表示每个节点处的理想角度之和，它和 $M$ 相等，所以

J = 2 (\sum k = 1 4 I k - B)

$J = 2\left(\sum_{k=1}^4I_k - B\right)$

下面分析 $G$ , 因为两个不同的节点不可能是同一个单元的第 $k$ 个顶点的，所以 $C_{N\times NT}^k$ 任意两行正交，则

D k = C k N \times N T (C k N \times N T) T

$D_k = C_{N\times NT}^k(C_{N\times NT}^k)^T$

是一个对角矩阵， $D_k(i,i)$ 是第 $k$ 个顶点为第 $i$ 个节点的单元的个数，可得对角矩阵

D = \sum k = 1 3 D k

$D = \sum_{k=1}^3 D_k$

其中 $D(i,i)$ 为第 $i$ 个节点的邻接单元个数。

记 $P = \sum_{k=1}^3 C_{N\times NT}^k$ , 则

P (i, j) = {1, 第 i 个 节 点 是 第 j 个 单 元 的 顶 点; 0, 否 则 .

$\begin{equation} P(i,j)= \begin{cases} 1, \text{ 第 }i\text{ 个节点是第 }j\text{个单元的顶点};\\ 0, \text{否则}. \end{cases} \end{equation}$

所以 $P$ 为节点和单元的邻接矩阵. 记 $Q = PP^T$ ，则

Q (i, j) = ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ 邻 接 单 元 的 个 数, i = j; 2, (i, j) 构 成 一 条 内 部 边; 1, (i, j) 构 成 一 条 边 界 边; 0, 其 它 .

$\begin{equation} Q(i,j) = \begin{cases} \text{邻接单元的个数}, i=j;\\ 2, (i,j)\text{ 构成一条内部边};\\ 1, (i,j)\text{ 构成一条边界边};\\ 0, \text{ 其它}. \end{cases} \end{equation}$

则 $-G = 3D - Q$ ，是三角形网格的 Laplacian 矩阵. 从图的理论出发，假设我们的网格为连通图，那么 $G$ 有且只有一个 0 特征值。

最优单元角度算法研究

一, 四边形网格

二, 三角形网格

三, 四面体网格

四, 六面体网格

最优单元角度算法研究

一, 四边形网格

二, 三角形网格

三, 四面体网格

四, 六面体网格

内容目录