algorithm - 如何将二叉树转换为多边形三角剖分，反之亦然

Question

根据 wikipedia ，在 n - 2 个节点的二叉树和简单的 n-vertex 多边形三角剖分之间存在双射(1:1 对应关系)。我想知道，如何相互转换*？
换句话说，如何将三角形集转换为二叉树以及如何将二叉树转换为三角形集？三角形是顶点 (v0, v1, v2) 的逆时针三元组并链接相邻三角形 (n0, n1, n2)。
* 从程序员的角度来看，算法、代码示例等

Answer 1

这是一个递归双射。

基本情况是退化的 2 顶点多边形对应于空树。

归纳地，树至少有一个内部节点。假设多边形的顶点具有按顺时针顺序从 1 到 n 的预先存在的标签。检查包含边 12 的唯一三角形 T。

   1-----2
  /|    /|\
 / | T / | \
6  |  /  |  3
 \ | /   | /
  \|/    |/
   5-----4

如果我们删除 T，我们会得到两个三角多边形。在这种情况下，我们得到 2345 和 156。递归地双射包含 1 的多边形以获得根的左子树。递归地对包含 2 的多边形进行双射以获得根的右子树。

查看此双射的一种特别巧妙的方法是，我们通过采用三角剖分的平面对偶图，删除入射到无限面的边，并将与 12 相邻的面指定为根来导出树。