Phát hiện tứ diện trong một lưới tam giác?

Question

Hãy nói rằng tôi có một lưới có đường kết nối các đỉnh theo một cách mà sẽ cho phép nó được chia thành tứ diện. Có một thuật toán tôi có thể sử dụng để phát hiện sự hiện diện của tứ diện cho các đỉnh và dòng? (Tức là, với lưới có các đường kết nối, xuất một tập hợp các tứ diện có hình dạng và thể tích giống nhau.)

Chỉnh sửa: tứ diện không được phép giao nhau.

Answer 1

Tôi nghĩ rằng phương pháp tiếp cận dựa trên biểu đồ có thể hoạt động.

Đầu tiên, danh sách các khuôn mặt hình tam giác có thể được phục hồi bằng cách lưu ý rằng tập hợp các cạnh xác định đồ thị vô hướng G1(V1,E1) để kết nối giữa các đỉnh hình học. Một mặt hình tam giác là bất kỳ chu kỳ 3 độ dài nào trong biểu đồ này.

for (i = all vertices in G1) 
// form list of vertex triplets 
    list = find all length 3 cycles from ith vertex 
// push new faces onto output 
    for (j = all triplets in list) 
     [v1,v2,v3] = list(j) 
     if ([v1,v2,v3] is not an existing face) 
      push triplet [v1,v2,v3] as a new face 
     endif 
    endfor 
endfor 

Tiếp theo, tứ diện đó có thể được phục hồi bằng cách hình thành đồ thị vô hướng G2(V2,E2) định khả năng kết nối giữa các mặt (ví dụ: khuôn mặt được kết nối nếu họ chia sẻ một cạnh). Một tứ diện là bất kỳ độ dài 4 chu kỳ trong biểu đồ này.

for (i = all vertices in G2) 
// form a list of face tuples 
    list = find all length 4 cycles from ith vertex 
// push new tetrahedra onto output 
    for (j = all tuples in list) 
     [f1,f2,f3] = list(j) 
     [v1,v2,v3,v4] = unique vertices in faces [f1,f2,f3] 
     if ([v1,v2,v3,v4] is not an existing tetrahedra) 
      push tuple [v1,v2,v3,v4] as a new tetrahedra 
     endif 
    endif 
endfor 

Hy vọng điều này sẽ hữu ích.