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:
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
It doesn't determine face ordering
I'm using frozenset
s 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)
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?