algorithm - 镶嵌的逆任务

Question

作为输入，我有一组三角形，它们形成带孔的凹面网格。每个三角形由三个顶点组成:(vi,vj,vk),... 没有提供邻接信息。算法必须将具有相同法线 的一组三角形“合并”为多边形。所以输出是 (pi,pj,pk,...,ps),...

例如(见下图)，假设我们有由三角形组成的网格

(v0,v1,v4), (v1,v3,v4), (v1,v2,v3)

(v2,v6,v4), (v6,v5,v4).

作为输出我们有:

(p0,p1,p4)

(p1,p2,p3,p4)

我正在寻找解决上述问题的高效算法。任何建议、提示或文章都将受到赞赏。

Answer 1

离开我的头顶；

• 对每个多边形进行三角剖分，得到一组三角形。
• 对于所有多边形中的所有三角形，根据法线分配一个组号
• 对于每个三角形 T = (va,vb,vc) 创建的邻接信息 E = (ab,bc,ca)，其中 ab 是在边 a,b 处与 T 相邻的三角形的链接/索引。
• 通过搜索两个相邻三角形不属于同一组的任何边来追踪每个新多边形的轮廓，跟随具有相同关系的下一条边，并重复直到回到第一条边。

请注意，您还必须应对 TIN 外壳边缘的 NULL 边缘类型，但这很简单。

这里最慢的一点是开发邻接信息，许多好的 TIN 创建算法可以在 O(n log n) 内完成。