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.

Answer 2

Given the information from Bartosz, this is what i came up with.

class vertex(object):
    def __init__(self, ID):
        self.ID = ID
        self.connected = set()

    def connect(self, cVertex):
        self.connected.add(cVertex.ID)

vertex_list = [vertex(ID) for ID in range(1,6+1)]
face_list = set()
edge_list = set()
edges.sort(key=lambda tup: tup[0] + tup[1]/10.0)
for (a,b) in edges:
    vertex_list[a-1].connect(vertex_list[b-1])
    vertex_list[b-1].connect(vertex_list[a-1])
    common = vertex_list[a-1].connected & vertex_list[b-1].connected
    if (common):
        for x in common:
            if not set([(x, a),(a, b),(b, x)]) & edge_list:
                face_list.add((x, a, b))
                edge_list.update([(x, a),(a, b),(b, x)])

            elif not set([(a, x),(x, b),(b, a)]) & edge_list:
                face_list.add((a, x, b))
                edge_list.update([(a, x),(x, b),(b, a)])

for face in face_list:
    print face

Answer 3

Implementation of this answer

from collections import defaultdict, deque
import itertools

def facetize(edges):
    """turn a set of edges into a set of consistently numbered faces"""

    # build lookups for vertices
    adjacent_vertices = defaultdict(set)
    for a, b in edges:
        adjacent_vertices[a] |= {b}
        adjacent_vertices[b] |= {a}

    orderless_faces = set()
    adjacent_faces = defaultdict(set)

    for a, b in edges:
        # create faces initially with increasing vertex numbers
        f1, f2 = (
            tuple(sorted([a, b, c]))
            for c in adjacent_vertices[a] & adjacent_vertices[b]
        )

        orderless_faces |= {f1, f2}
        adjacent_faces[f1] |= {f2}
        adjacent_faces[f2] |= {f1}


    def conflict(f1, f2):
        """returns true if the order of two faces conflict with one another"""
        return any(
            e1 == e2
            for e1, e2 in itertools.product(
                (f1[0:2], f1[1:3], f1[2:3] + f1[0:1]),
                (f2[0:2], f2[1:3], f2[2:3] + f2[0:1])
            )
        )

    # state for BFS
    processed = set()
    to_visit = deque()

    # result of BFS
    needs_flip = {}

    # define the first face as requiring no flip
    first = next(orderless_faces)
    needs_flip[first] = False
    to_visit.append(first)

    while to_visit:
        face = to_visit.popleft()
        for next_face in adjacent_faces[face]:
            if next_face not in processed:
                processed.add(next_face)
                to_visit.append(next_face)
                if conflict(next_face, face):
                    needs_flip[next_face] = not needs_flip[face]
                else:
                    needs_flip[next_face] = needs_flip[face]


    return [f[::-1] if needs_flip[f] else f for f in orderless_faces]