将三角形带的顶点转换为多边形的算法

Question

我有一个数组，其顶点代表三角形带。 我需要将其转换为多边形。 有很多解决方案可以进行相反的操作，但我未能找到解决上述问题的方法。 或者它可能太容易了，我只是看不到它。 请帮忙。

OpenGL=兼容，请参阅 http://en.wikipedia.org/wiki/Triangle_strip

示例： 对于此条 http://en.wikipedia.org/wiki/File:Triangle_Strip_Small.png< /a> 我需要输出 ABDFEC 或 ACEFDB

Answer 1

如果您的形状具有特别简单的结构，可能有一个快捷方式，但一般来说，我认为您想要执行以下操作：

• 从三角形列表中创建顶点和边的列表。这涉及到检测共享点（希望它们是完全匹配的，这样您就可以通过散列找到它们，而不需要某种模糊搜索）和共享线（这很简单 - 只是不要在同一对共享顶点之间绘制两条边） 。
• 找到最左上角的点。
• 找到尽可能位于左上角且逆时针方向的边。
• 走到下一个顶点。
• 找到下一条边，尽可能地在前一条边上加倍。
• 继续前进，直到再次到达最左上角的点。

Answer 2

我相信以下方法应该有效：

遍历顶点列表。将第一个点添加到多边形中。将第二个点压入堆栈。将第三个点添加到多边形中。继续交替推入堆栈上的点并将它们添加到多边形中，直到到达列表的末尾。当到达列表末尾时，弹出堆栈中的点并将它们添加到多边形中。

Answer 3

我假设你的三角形带总是以相同的方式连接（我相信对于 OpenGL 来说也是如此）。

• “底部”顶点始终是两个
  分开：A、C、E……
• “顶部”
  顶点始终相距两个：B、D、
  F，...

获取“底部”列表并附加“顶部”列表的相反内容。 （以 ACEFDB 为例）

---

或者，更直接地，使用从零开始的索引而不是字母：

// do "bottom"
for ( i = 0; i < N; i += 2 )
  addVertex( i )

// do "top"
largestOddNumberLessThanN = N % 2 == 0 ? N - 1 : N - 2;
for ( i = largestOddNumberLessThanN; i >= 0; i -= 2 )
  addVertex( i )