Найти грани, соединенные с вершиной

Скажем, у меня есть тетраэдр, построенный из треугольников (или граней), каждый треугольник содержит три вершины. Тетраэдер представлен следующим образом:

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]

Создание словаря занимает некоторое время (180 мс для меша с 55 000 граней), но последующие запросы выполняются почти мгновенно. В то время как функция @bb1 на моем компьютере занимала 7 мс на один запрос.

person ThaNoob    schedule 02.04.2021