有没有一个Python库可以计算三维网格的对偶？

Question

我查看了python-graph和boost graph库的python绑定，但没有找到关于网格对偶化的相关内容（对偶图的顶点是原始图的面，并且如果它们在原始图中共享一个边，则在对偶图中由一条边连接）。在我重新发明轮子之前，我是否可能忽略了某个实现？

- Noam Kremen

Answer 1

可能存在这样的算法，但实现起来非常简单。要做到这一点，需要找到使用该边的三角形。有了这些信息，就可以在三角形之间建立连接。

以下是一个简单的Python实现，其中三角形（或多边形）是顶点索引列表，边是顶点索引的有序对：

from collections import defaultdict
from itertools import combinations
triangles = [(1,2,3), (2,3,4), (1,3,5), (3,4,5), (5,6,7), (4,5,6)]
# For each edge set triangles containing that edge
edge2trias = defaultdict(list)  # edge (v1,v2) -> list of triangles
for t_ind, ps in enumerate(triangles):
    for edge in zip(ps, ps[1:]+ps[:1]):
        edge2trias[tuple(sorted(edge))].append(t_ind)
# For each edge, set pair(s) of neighbouring triangles
tria2neigh = defaultdict(list)  # triangle index -> list of neighbouring triangles
for edge, trias in edge2trias.iteritems():
    for t1, t2 in combinations(trias, 2):
        tria2neigh[t1].append(t2)
        tria2neigh[t2].append(t1)

- Ante

---

是的，最终得到了非常相似的实现。 - Noam Kremen

Answer 2

回答自己的问题 - graph-tool的线图函数 计算图的对偶。

- Noam Kremen