mesh - 三角网状拓扑

Question

我有一个三角形网格类，其中包含一个节点列表(在我的情况下为 2d，但这无关紧要)和一个面列表。每个面都是一个三角形，它只包含节点数组的索引。网格来自 Delaunay 算法，因此非常干净。

对于网格中的每个节点，我需要找到哪些节点通过一条边连接到它。构建和搜索此拓扑数据库的快速方法是什么？

多谢，
大卫·鲁顿

Answer 1

有两种标准的数据结构可以促进网状拓扑查询。一个是Winged Edges (通常也称为 half-edge )，另一个是 Directed Edges .谷歌一下，你会得到无数的细节，以及每一个细节的不同层次的介绍。

对您的方案了解不足，无法推荐其中之一。例如，有向边是存储优化的，最适合非常大的网格。有翼的边缘被认为是“经典”，是更高级 flavor 的良好起点。

实际上，如果您确定这是您需要的唯一查询，那么两者都是矫枉过正，您可以使用单个散列来完成。但是，如果您发现自己需要对诸如以下问题的有效答案 -

哪些面使用这个顶点？

哪些边使用这个顶点？

哪些面与这条边接壤？

哪些边与这张脸接壤？

哪些面与此相邻
脸？

您应该考虑深入其中之一。