У меня есть некоторые данные, которые выглядят следующим образом:
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!
}
Однако это плохо для two причин:
-
Он по крайней мере O (N³)
В этом конкретном случае это не проблема, так как N = 10242, она завершается менее чем за 5 секунд
-
Он не определяет порядок лиц
Я использую
frozensetтам, которые по своей сути беспорядочны. Мне нужно создать грани с таким же циклическим порядком, как и мой пример.Созданные последовательности лиц используются для рендеринга односторонней поверхности с OpenGL. В результате важно, чтобы все вершины граней находились в одном и том же ротационном порядке (независимо от того, находится ли это по часовой стрелке или против часовой стрелки, является свойством самих вершин), все, о чем я забочусь, состоит в том, что каждая грань одинакова)
-
Предполагается, что все ребра, образующие треугольник, должны быть гранью
Как отмечает @Bartosz в комментариях, этого не должно быть: возьмите любые две треугольные сетки и присоедините их к лицу, и у вас есть нечто, что уже не лицо.
Какой метод я должен использовать для построения списка граней с правильным порядком вращения?
