构造一个多边形的轮廓（特别是三角形）

Question

我该如何去构造二维多边形的轮廓，它只由三角形构成，它可以有孔，外部轮廓可以是凹凸的，并且孔可以也是凹面/凸面。

从什么I'm reading over here看来，它恰好是三角测量问题的反面。 你是否知道处理这类问题的任何文章？

八叉树/四叉树是否与此相关？

Answer 1

我想你有三组数据，它们构成一个“填充”三角形，这些三角形沿着边连接，并且所有将是完整形状的角的顶点也是顶点触及这一点的所有三角形。那么你只需要找到所有不加倍的边，即不属于两个相邻的三角形。

Answer 2

我认为你可以通过创建一个拓扑数据结构来表示你的三角形集合，然后使用该结构在位于边界上的三角形边缘上依次迭代来解决你的问题。

例如：你可以创建一个halfedge数据结构。假设你在边界上（正确地）插入半边，遍历边界轮廓就像在边界上定位一个半边，然后迭代它的“下一个”指针一样简单，直到你回到你开始的半边。

类似于halfedges，你可以使用其他拓扑结构，如翼边等，但概念是相同的。