How can I construct a list of faces from a list of edges, with consistent vertex ordering?

Question

I have some data that looks like this:

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

The example above describes an octohedron - numbering the vertices 1 to 6, with 1 and 6 opposite each other, each entry describes the vertex numbers at the ends of each edge.

From this data, I want to produce a list of faces. The faces are guaranteed to be triangular. Here's one such face list for the input above, determined by hand:

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

Diagramatically, this can be represented as follows:

For any face, follow the direction of the curled arrow, and you can read off the vertex numbers above. This doesn't really work for the outer face, 1, 3, 4, but you can fix that by drawing on the surface of a sphere

---

I can get close with this:

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)

Giving (reordered from output for ease of comparison with the original):

[
    (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!
}

However, this is bad for two reasons:

1. It's at least O(N³)

   In this particular case, that's not a problem, since N = 10242, it completes in less than 5 seconds

2. It doesn't determine face ordering

   I'm using frozensets there, which are inherently orderless. I need to produce faces with the same cyclic order as my example output.

   The face sequences generated are used to render one-sided surface with OpenGL. As a result, it's essential that all the faces vertices are in the same rotary order (whether that ends up being clockwise or anticlockwise is a property of the vertices themselves - all I care about is that each face is the same)

3. It assumes all edges that form a triangle must be a face

   As @Bartosz points out in the comments, this needn't be the case - take any two triangular meshes, and join them at a face, and you have something that is no longer a face.

---

What method should I be using to construct a list of faces with the correct rotational order?

Answer 1

I can give you a clue with the second part; once you have the faces, there is a simple way of making it cyclically correct.

Start with choosing one face (a, b, c) to be correct, then no other face can contain (a, b), (b, c) or (c, a) in that order. In other words, find face that contain vertices a, b then make it be (b, a, x), and so on.

In case you don't get what I mean - use the following fact: each edge (x, y) is contained by two faces, and if they are cyclically correct, one of the faces has it as (x, y), the other as (y, x).

Possible implementation: Start with creating a graph where faces are vertices and edges mean that two faces share an edge in the original problem. Then use DFS or BFS.