python - 3D メッシュのデュアルを計算できる Python ライブラリはありますか?

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 の折れ線グラフ機能 は、グラフの双対を計算します。