Как я могу построить список граней из списка ребер с последовательным упорядочением вершин?

У меня есть некоторые данные, которые выглядят следующим образом:

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 в комментариях, этого не должно быть: возьмите любые две треугольные сетки и присоедините их к лицу, и у вас есть нечто, что уже не лицо.

Какой метод я должен использовать для построения списка граней с правильным порядком вращения?

Ответы

Ответ 1

Я могу дать вам подсказку со второй частью; когда у вас есть лица, есть простой способ сделать его циклически правильным.

Начните с правильного выбора одного лица (a, b, c), тогда никакое другое лицо не может содержать (a, b), (b, c) или (c, a) в этом порядке. Другими словами, найдите грань, содержащую вершины a, b, затем сделайте ее (b, a, x) и т.д.

Если вы не понимаете, что я имею в виду, используйте следующий факт: каждое ребро (x, y) состоит из двух граней, и если они циклически правильны, одна из граней имеет его как (x, y), другой - (y, x).

Возможная реализация: Начните с создания графа, где лица - это вершины и ребра, означающие, что две грани разделяют край в исходной задаче. Затем используйте DFS или BFS.

Ответ 2

Учитывая информацию из Бартоша, это то, с чем я столкнулся.

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

Ответ 3

Выполнение этого ответа

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]