文章/答案/技术大牛

发布

社区首页 >问答首页 >如何将二叉树转换为多边形三角剖分，反之亦然

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

Stack Overflow用户

提问于 2014-11-29 17:34:59

回答 1查看 1.1K关注 0票数 1

根据维基百科，n-2节点二叉树与简单的n-顶点多边形三角剖分之间存在双射(1:1对应)。我想知道，如何在彼此之间转换*

换句话说，如何将一组三角形转换为二叉树，如何将二叉树转换为三角形集合？三角形是由顶点(v0，v1，v2)和连接邻域三角形(n0，n1，n2)组成的ccw三重奏。

*从程序员的角度来看，算法、代码示例等等。

algorithm

binary-tree

polygon

triangulation

回答 1

Stack Overflow用户

回答已采纳

发布于 2014-11-30 00:37:57

这里有一个递归双射。

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

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

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

如果删除T，则得到两个三角多边形。在这种情况下，我们得到2345和156。递归地弹出包含1的多边形，以得到根的左子树。递归地弹出包含2的多边形，以获得根的正确子树。

考虑这种双射的一个特别巧妙的方法是，我们通过采用三角剖分的平面对偶图，删除与无限面相关的边，并指定与12相邻的面作为根来导出树。

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/27204998

复制

相似问题

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

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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