重建三角形网格中的所有边

Question

我有一个包含数百万个三角形的三角形网格。目前，在我的数据结构中，只存储三角形和顶点。我想重建所有的边，并将它们存储在一个数据容器中。这个想法可能是这样的：遍历所有三角形，得到它的每两个顶点，并在它们之间创建一条边。问题是共享边缘可能会创建两次。因此，为了克服这个问题，我需要一个数据容器EdgeContainer来存储边，它应该有一个功能来检查这个边是否已经创建。所以它就像一个有多个键的地图，但根据我的问题，这个地图还应该有以下功能：

1. EdgeContainer(v1, v2)应该返回与EdgeContainer(v2, v1)相同的结果，其中v1和v2是指向两个顶点的指针
2. EdgeContainer应该具有类似于EdgeContainer::Remove(v1)的函数，该函数将移除入射到顶点v1的所有边
3. 执行工作应尽可能高效

是否有任何现有的库可以处理此问题？

Answer 1

首先，我建议您了解半边缘http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml网格——它在CGAL和OpenMesh中都有使用，你应该知道你将要使用其中任何一个的概念。我推荐OpenMeshhttp://openmesh.org/Documentation/OpenMesh-2.0-Documentation/tutorial_01.html它是免费和开源的，您可以从一组顶点和索引轻松创建网格，创建网格后，您可以轻松地在所有边上迭代。

Answer 2

最简单的选择是使用Cgal库，它基本上是为实现这一点而设计的。

http://doc.cgal.org/latest/Triangulation_2/index.html

它提供了用于在面、边和顶点上进行迭代的自然迭代器。

请注意，在Cgal中，它们实际上并没有显式存储边，而是生成的每次迭代结构时。使用一些巧妙的规则可以有效地做到这一点这可以阻止你数两次：看看代码，似乎每个人脸迭代一次并且为每个相邻面向当前面添加边，在面列表中比当前面更早出现的面。

请注意，以这种方式访问边缘只需要每个边缘恒定的时间(取决于您存储面部的方式)，因此您不太可能从单独存储它们中获益。还要注意，边是由两个相邻的面定义的，而不是由两个邻近的顶点定义的。你可以在恒定的时间内变换它们。

Answer 3

简单的解决方案是使用排序的索引对：

struct _edge_desc : public std::pair<int,int> {
_edge_desc(int a, int b): std::pair<int,int>(a<b?a:b, a<b?b:a) {}
};
std::set<_edge_desc> Edges;

如果需要关于边的额外信息，则可以将其存储在单独的向量中，并且不使用存储边的集合，而是使用映射到向量中索引的映射。

std::vector<some_struct> EdgesInfo;
std::map<_edge_desc, int> EdgesMap;