度量的平面嵌入(Planar Metric Embedding)算法

在离散黎曼几何中，里奇流(Ricci Flow)、卡拉比流(Calabi Flow)、Yamabe Flow等几何学流动的结果都是一组度量(Metric)的形式，即我们直到的仅仅是结果的一组边长。在基于这些方法的平面参数化里，必须将结果嵌入到欧氏空间中得到所有点的坐标。

将度量嵌入到欧氏空间，或者说从边长得到坐标，是一个看似简单实则坑点满满的问题，常规的数值优化方法常常会陷入局部最优无法自拔。对于一般情形下的解决方法，可以参阅SIGGRAPH 2018的一篇论文Shape From Metric。本文介绍的是一个特殊得多的平面情况。

对于球面的情况，可以参阅这篇文章。

方法一：相交圆法

1. 在平面中，我们可以很容易地先嵌入第一条边AB。
2. 对于已嵌入的边AB，在三角形ABC中，已知AB坐标、|AC|和|BC|，求C点坐标可以分别以A点和B点为圆心，作半径为|AC|和|BC|的两个圆，两圆的2个交点即是满足三角形ABC度量的C点的取值。如下图所示。
3. 对于C点的2个取值，需要作出一定的筛选，例如，规定使三角形ABC逆时针方向上的法向量朝Z+方向。确定C点后，相当于又嵌入了更多的边。
4. 重复2-3，直到所有顶点嵌入完毕。

相交圆法的理解很简单，不过缺点在于需要对结果作出筛选，这虽然不会对性能造成特别大的影响， 但整体流程不是特别优美。

方法二：向量法

向量法适用于半边数据结构。在半边数据结构中，任意一条半边指向的面是确定的，如在OpenMesh中，半边A->B所指向的面遵循左手定则：使向量A->B为左手四个手指的方向，则左手拇指方向为半边A->B所指向的面。如图所示。

在这个前提下，对于任意一条已嵌入的半边A->B，我们可以唯一确定三角形ABC中点C的方向。对应的算法如下（下面简记半边A->B为半边AB）：

1. 在平面中，我们可以很容易地先嵌入第一条边AB，在嵌入边AB时也得到了嵌入的半边AB和半边BA。
2. 对于已嵌入的半边AB，在三角形ABC中，已知|AB|、|AC|和|BC|，进而已知所有角。如图所示，我们可以求得向量At=AB * (|AB| - |BC| * cosB)，以及向量tC的方向为(-AB[1], AB[0])、长度为|BC| * sinB。故C点坐标可以由A点坐标和向量At、向量tC得到。确定C点后，相当于又嵌入了更多的半边。
3. 重复2，直到所有顶点嵌入完毕。