Намерете лица, свързани с върха

Да кажем, че имам тетраедър, който е изграден от триъгълници (или лица), всеки триъгълник съдържа три върха. Тетраедърът е представен по следния начин:

vertices = [[0. 0. 0.] [0. 1. 1.] [1. 0. 1.] [1. 1. 0.]]
faces = [[0 1 2] [0 2 3] [0 1 3] [1 2 3]]

Бих искал да имам структура, на която мога да дам индекс на върха и да ми върне лицата, които съдържат този връх по ефективен начин. Трябва да е ефикасно, тъй като трябва да намеря лицата, свързани например с 1000 върха във файл с 20 000 лица. Следователно трябва да бъде някакъв вид структура от данни, където елемент от структурата е списък от лица и индексът на този елемент е равен на индекса на върха, който е свързан с тези лица.

Например: върнете индексите на лицето на лицата, свързани към върха с индекс 1, трябва да изглежда така:

vertex_index = 1
find_connected_faces[vertex_index] --> [0,2,3]

Отговорът трябва да бъде [0,2,3], защото върхът с индекс 1 ([0. 1. 1.]) присъства в тези лица. Затруднявам се да намеря начин да разреша този проблем ефективно. Мислех за графики, използващи библиотеката networkx, но не намерих най-добрия подход. Намерих много решения за намиране на две лица, които са свързани с ръб, но както виждате, това не е точно това, което търся.


python mesh
person ThaNoob    schedule 01.04.2021    source източник

Отговори (2)


arrow_upward
1
arrow_downward

Ето един начин да го направите:

def find_connected_faces(vertex_index, faces):
    return [faces.index(f) for f in faces if vertex_index in f]

По същия начин, използвайки numpy:

import numpy as np

def find_connected_faces(vertex_index, faces):
    return np.nonzero(np.array(faces) == vertex_index)[0]
person bb1    schedule 01.04.2021
comment
Благодаря за отговора @bb1, това е много елегантно решение като еднократна функция. Представете си обаче, че трябва да потърся хиляди точки, след което за всяко търсене нагоре трябва да премина през всички лица. Всъщност си мислех за метод, при който кодът преминава веднъж през всички лица и създава подобна на списък структура, където индексът представлява индекса на върха и елементът в този списък за този индекс съдържа индексите на лицата, където присъства този връх . - person ThaNoob; 02.04.2021
comment
Редактирах въпроса, така че въпросът да отразява това, което споменах в предишния коментар - person ThaNoob; 02.04.2021

arrow_upward
0
arrow_downward

Намерих начин да го направя доста ефективно благодарение на @bb1 и следното публикация.

faces_connected_to_vertex = {}
vertices = [[0, 0, 0],[0, 1, 1], [1, 0, 1], [1, 1, 0]]
faces = [[0, 1, 2], [0, 2, 3], [0, 1, 3], [1, 2, 3]]
for face_index,face in enumerate(faces):
    for vertex_index in face:
        faces_connected_to_vertex.setdefault(vertex_index,[]).append(face_index)

Резултатът е речник с ключове индексите на върховете и стойности индексите на свързаните лица. Ако индексът на върха вече съществува в речника, тогава индексът на лицето се добавя към списъка с лица, ако все още не съществува, тогава се прави нов ключ със списък с единствената стойност на този индекс на лицето.

За този пример:

faces_connected_to_vertex[1] --> [0,2,3]

Изграждането на речника отнема известно време (180ms за мрежа с 55 000 лица), но заявките след това са почти мигновени. Докато функцията на @bb1 отне 7ms на моята машина за една заявка.

person ThaNoob    schedule 02.04.2021