遍历由相连三角形组成的多边形的边界点
我有一个由连接的三角形组成的二维多边形网格，如下所示：
- 顶点数组：
V = A，B，C，D，E，... - 索引数组，三角形顶点索引按逆时针顺序为 3 个一组：
I = 0, 4, 3, ...
（例如，V[0]、V[4]、V[3]（即AED）形成一个三角形）
http://img694.imageshack.us/img694/8968/meshg.png 网格示例
现在我想以逆时针顺序遍历边界点，起始顶点并不重要：G、H、A、D、C、F
这样做的原因是我想计算动态 2D 阴影，如本文中所示： http://www.gamedev.net/reference/programming/features/2dsoftshadow/page3.asp
最好的方法是什么做这个吗？我考虑过计算凸包，但这似乎太昂贵了，因为它没有使用三角形顶点索引，必须有更好的方法。
有没有一种方法可以使其甚至适用于一个表示中的多个多边形，以便我获得每个连接的多边形的边界点列表列表？
谢谢，阿本西
I have a two dimensional polygon mesh made of connected triangles represented like this:
- vertex array:
V = A, B, C, D, E, ... - index array, triangle vertex indices in groups of 3 in counter-clockwise-order:
I = 0, 4, 3,
...
(so that e.g.V[0], V[4], V[3]which isA-E-Dforms a triangle)
http://img694.imageshack.us/img694/8968/meshg.png
Example mesh
Now i want to traverse the boundary points in counter-clockwise-order, the starting vertex doesn't matter:G, H, A, D, C, F
The reason for this is that i want to compute dynamic 2D shadows like in this article: http://www.gamedev.net/reference/programming/features/2dsoftshadow/page3.asp
Whats the best way to do this? I thought about computing a convex hull, but this seems too expensive because it's not using the triangle vertex indices, there has to be a better way.
Is there a way to make it work even for several polygons in one representation so that i get a list of boundary point lists for every connected polygon?
Thanks, abenthy
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这是一种方法：
(A, B)与(B, A)) 是同一条边。由于三角形是逆时针方向，计算出的边界也将是逆时针方向。这种方法很好，因为它不需要顶点的实际位置，它只使用索引指定的拓扑。
Here's one way:
(A, B)is the same edge as(B, A)).Since the triangles are counter clockwise the computed boundary will also be counter clockwise. This method is good because it doesn't need the actual positions of the vertices, it only uses the topology specified by the indices.