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

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

EdgeContainer(v1, v2)应该返回相同的结果EdgeContainer(v2, v1)，其中v1和v2是指向两个顶点。
EdgeContainer应该有一个功能类似EdgeContainer::Remove(v1)，这将删除所有边缘事件到顶点v1。
实施应尽可能高效。

是否有可以处理这个任何现有的图书馆吗？

来源

2014-03-05 C. Wang

为什么不能简单'map >'不够？ –

@NicoSchertler，'Edge'必须明确地存储以供进一步使用，即存储其长度或一些其他属性。你的建议无法处理它，可以吗？ –

然后让它'map >'。 –

你最简单的选择将是使用CGAL库，这基本上是专为做这个。

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

它提供自然的迭代器用于遍历面，边和顶点。在CGAL，他们实际上并不保存边缘明确

通知，他们每个结构迭代时产生。这可以有效地利用一些聪明的规则阻止你计数的事情两次完成：看代码，似乎每个面被重复一次，并且边缘添加了对来自每个相邻面对当前面，在面孔列表中比当前面孔更早。

请注意，以这种方式访问边缘只需要每边缘固定时间（这取决于你如何存储你的脸），这样就不可能从单独存放受益。另请注意，边缘由两个相邻的面定义，而不是两个相邻的顶点。你可以在一段时间内改变它们。

来源

2014-03-05 20:53:12

首先，我建议你看看半角http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml网格它在CGAL和OpenMesh中使用的概念，你应该知道你将使用它们中的任何一个的概念。我的slef建议OpenMesh http://openmesh.org/Documentation/OpenMesh-2.0-Documentation/tutorial_01.html它是免费且开源的，您可以轻松地从顶点和索引集创建网格，并且在创建网格后，您可以轻松地遍历所有边缘。

来源

2014-03-06 09:55:10

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

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;

来源

2014-03-06 10:38:57 Ante

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

回答

相关问题