如何从边列表构造一个面列表,具有一致的顶点排序？

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)
]

从图形上看,这可以表示如下:

对于任何面,按照卷曲箭头的方向,您可以读取上面的顶点数字.这不适用于外表面,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那里使用s,这本身就是无序的.我需要生成与我的示例输出具有相同循环次序的面.

   生成的面部序列用于使用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。