如何使用一致的頂點排序從邊緣列表構造一個面的列表？

Question

我有一些數據，看起來像這樣：

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

上面的實施例描述了octohedron - 編號的頂點爲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! 
} 

然而，這是不好的原因：

1. 它至少O（N 3）

   在這個特定的情況下，這不是一個問題，因爲N = 10242，它在小於5秒

2. 一點也沒有完成't確定臉訂購

   我在那裏使用frozenset，這本質上是無序的。我需要以與我的示例輸出相同的循環順序生成面。

   生成的臉部序列用於使用OpenGL渲染單面曲面。因此，所有面頂點必須是相同的旋轉順序（不管是順時針還是逆時針是頂點本身的屬性 - 我只關心每個面都是相同的）

3. 它假定形成三角形必須面對一個所有邊緣

   由於@Bartosz在評論中指出，這不是必須的情況下 - 採取任何兩個三角形網格，並在迎面加入他們的行列，並你擁有的東西不再是一張臉。

---

我應該用什麼方法來構造面的列表與正確的旋轉次數？

Answer 1

我可以給你一個線索，第二部分;一旦你有了面孔，有一個簡單的方法可以使其循環糾正。

從選擇一個面（a，b，c）開始選擇正確的，然後沒有其他面可以按順序包含（a，b），（b，c）或（c，a）。換句話說，找到包含頂點a，b的面，然後使其成爲（b，a，x），依此類推。

如果您沒有明白我的意思 - 請使用以下事實：每個邊（x，y）由兩個麪包含，如果它們是循環正確的，則其中一個面具有（x， y），另一個爲（y，x）。

可能的實現方式： 從創建一個圖形開始，其中面是頂點和邊意味着兩個面在原始問題中共享邊。然後使用DFS或BFS。

Answer 2

鑑於來自Bartosz的信息，這就是我想出的。

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

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