我有一个网格,其中包含某些类型的元素(例如三角形、四边形)。对于每个元素,我知道它的所有顶点,即三角形 2D 元素将有 3 个顶点 v1、v2 和 v3,它们的 x、y、z 坐标是已知的。
问题一
我正在寻找一种将返回所有边的算法...在这种情况下:
边缘(v1,v2),边缘(v1,v3),边缘(v2,v3)。根据每个元素有多少个顶点,该算法应该有效地确定边。
问题二
我正在使用 C++,那么,存储上述算法返回的边信息的最有效方法是什么?例如,我只对一个元组 (v1, v2) 感兴趣,我想将其用于某些计算然后忘记它。
谢谢
最佳答案
可以使用半边数据结构。
基本上你的网格也有一个边缘列表,并且每个方向上的每对顶点都有一个边缘结构。这意味着如果你有顶点 A 和 B,那么在某处存储了两个边缘结构,一个用于 A->B,一个用于 B->A。每条边有 3 个指针,一个称为 previous,一个称为 next,一个称为 twin。跟随下一个和上一个指针将引导您绕过网格中三角形或多边形的边缘。调用 twin 会将您带到相邻多边形或三角形中的相邻边。 (查看图片中的箭头)这是我所知道的最有用和最详细的边缘数据结构。我已经使用它通过创建新边和更新指针来平滑网格。顺便说一句,每条边也应该指向一个顶点,这样它就知道它在空间中的位置。
关于c++ - 使用网格中的顶点(2D 和 3D)查找边的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2294032/