python - 如何从边列表中构建面列表，并使顶点顺序一致？

Question

我有一些看起来像这样的数据:

vertex_numbers = [1, 2, 3, 4, 5, 6]

# all order here is unimportant - this could be a set of frozensets and it would
# not affect my desired output. However, that would be horribly verbose!
edges = [
    (1, 2),
    (1, 3),
    (1, 4),
    (1, 5),

    (2, 3),
    (3, 4),
    (4, 5),
    (5, 2),

    (2, 6),
    (3, 6),
    (4, 6),
    (5, 6)
]

上面的例子描述了一个八面体 - 将顶点编号为 1 到 6，1 和 6 彼此相对，每个条目描述了每条边末端的顶点编号。

根据这些数据，我想生成一个面孔列表。这些面保证是三角形的。这是上面输入的一个这样的面孔列表，由手工确定:

faces = [
    (1, 2, 3),
    (1, 3, 4),
    (1, 4, 5),
    (1, 5, 2),
    (2, 5, 6),
    (3, 2, 6),
    (4, 3, 6),
    (5, 4, 6)
]

在图表上，这可以表示如下:

对于任何面，按照 curl 箭头的方向，你可以读出上面的顶点编号。这对于外面 1, 3, 4 确实不起作用，但您可以通过在球体的表面上绘制来解决这个问题

---

我可以接近这个:

edge_lookup = defaultdict(set)
for a, b in edges:
    edge_lookup[a] |= {b}
    edge_lookup[b] |= {a}

faces = set()
for a in vertex_numbers:
    for b in edge_lookup[a]:
        for c in edge_lookup[a]:
            if b in edge_lookup[c]:
                faces.add(frozenset([a, b, c]))

faces = map(tuple, faces)

给予(从输出中重新排序以便于与原始比较):

[
    (1, 2, 3),  # ok
    (1, 3, 4),  # ok
    (1, 4, 5),  # ok
    (1, 2, 5),  # cyclically incorrect!
    (2, 5, 6),  # ok
    (2, 3, 6),  # cyclically incorrect!
    (3, 4, 6),  # cyclically incorrect!
    (4, 5, 6),  # cyclically incorrect!
}

但是，由于两个原因，这很糟糕:

1. 至少是 O(N³)

   在这种特殊情况下，这不是问题，因为 N = 10242，它在不到 5 秒内完成

2. 它不决定人脸顺序

   我在那里使用 frozenset，它们本质上是无序的。我需要生成与我的示例输出具有相同循环顺序的面孔。

   生成的面部序列用于使用 OpenGL 渲染单侧表面。因此，所有面的顶点都必须处于相同的旋转顺序(无论最终是顺时针还是逆时针是顶点本身的属性 - 我只关心每个面都是相同的)

3. 假设构成三角形的所有边都必须是面

   正如@Bartosz 在评论中指出的那样，情况不一定如此 - 取任意两个三角形网格，并将它们连接到一个面，你得到的东西不再是面。

   <

---

我应该使用什么方法来构建具有正确旋转顺序的面孔列表？

Answer 1

我可以给你第二部分的线索；有了面孔后，有一种简单的方法可以使其循环正确。

从选择一张脸 (a, b, c) 开始是正确的，然后没有其他脸可以按此顺序包含 (a, b)、(b, c) 或 (c, a)。换句话说，找到包含顶点 a、b 的面，然后将其设为 (b, a, x)，依此类推。

如果你不明白我的意思 - 使用以下事实:每条边 (x, y) 包含在两个面中，如果它们循环正确，其中一个面将它作为 (x, y ), 另一个为 (y, x).

可能的实现:从创建一个图形开始，其中面是顶点，边意味着两个面在原始问题中共享一条边。然后使用 DFS 或 BFS。