Есть ли библиотека питонов, способная вычислять дуал трехмерной сетки?

Question

Я изучил python-graph и привязки python для библиотеки графов надстроек, но не нашел ничего релевантного в отношении дуализации ячеек (вершины двойственности - это грани исходного графа и связаны ребром в двойственности. если они разделяют ребро в исходном графике) . Прежде чем я решу заново изобрести это колесо, есть ли реализация, которую я мог упустить из виду?

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)

Answer 2

И чтобы ответить на собственный вопрос - функция линейного графа Graph-Tool вычисляет двойственный график.