Большая, в основном пустая структура данных для граней тетраэдра

Я пытаюсь связать идентификатор узла каждого лица в тетраэдре с соответствующим ему идентификатором тетры.

tetras = [1 2 3 4  % Tetra 1
          5 6 7 8] % Tetra 2

Для тетры 1 есть четыре лица:

faces = [1 2 3; 1 2 4; 1 3 4; 2 3 4] % Notice these are sorted

Затем я хотел бы сохранить их в структуре данных:

tet_for_face = cell(8,8,8) % 8 allows for the maximum node id

tet_for_face{1,2,3} = 1;
tet_for_face{1,2,4} = 1;
tet_for_face{1,3,4} = 1;
tet_for_face{2,3,4} = 1;

Это означает, что я могу найти тетра-ID любого конкретного лица в O (1):

tet_for_face{2,3,3}
ans = []
tet_for_face{2,3,4}
ans = 1

Проблема этого подхода в том, что он требует непрерывной памяти. Когда моя сетка становится больше, мне не хватает памяти:

cell(1000, 1000, 1000)
??? Error using ==> cell
Out of memory. Type HELP MEMORY for your options.

Я также поиграл с использованием вложенных ячеек:

tet = cell(num_nodes, 1);
tet2 = cellfun(@(x) cell(num_nodes, 1), tet, 'UniformOutput', 0);
tet3 = cellfun(@(x) cellfun(@(y) cell(num_nodes, 1), x, 'UniformOutput', 0), tet2, 'UniformOutput', 0);

tet3{2}{3}{4} = 1;
...

Хотя это работает для небольших сеток и не требует непрерывной памяти (AFAIK), у него есть неприятная привычка разбивать MATLAB с N=1000.

Есть идеи?

Источник

2 ответа

Решение

После небольшой игры с разреженными массивами (которые могут быть только 1D или 2D, а не 3D) и никуда не попал, я решил пойти с контейнерами. Карта (HashMap).

Я использовал строковые ключи, и я нашел самый быстрый способ их создания, используя sprintf (вместо int2str или mat2str)

Образец кода:

tet = containers.Map;
for tetra_id in tetras 
    for face in faces
        face_key = sprintf('%d ', face);
        tet(face_key) = tetra_id;

Это дает мне карту примерно так:

tet('1 2 3') = 1
Источник

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

% tetras and faces are transposed - column-wise storage
tetras = [1 2 3 4; 5 6 7 8]';
faces = [1 2 3; 1 2 4; 1 3 4; 2 3 4]';

ntetras    = size(tetras, 2);
nfaces     = size(faces, 2);
nfacenodes = size(faces, 1);

% construct face definitions for all tetras
tetras_faces = reshape(tetras(faces, :), nfacenodes, ntetras*nfaces);

% assign the faces to tetras keeping the face id within the tetra, if you need it
enum_faces  = repmat(1:ntetras*nfaces, nfacenodes, 1);

% create a sparse matrix connecting tetra faces to tetras.
% Every column contains 3 non-zeros - 1 for every node in a face
% The number of matrix columns is ntetras*nfaces - 4 columns for every element.
A = sparse(tetras_faces, enum_faces, 1);

Теперь, чтобы извлечь нужную информацию, вы можете умножить A на вектор, содержащий информацию о лице, которое вы ищете:

v = sparse(ntetras*nfaces, 1);
v([1 2 3]) = 1;
tetra_id = ceil(find(A*v==nfacenodes)/nfaces)

Обратите внимание, что это всего лишь пример. Таким способом вы можете извлечь гораздо больше полезной информации и выполнить более сложные поиски, используя умножение матрицы на матрицу вместо умножения матрицы на вектор.

Источник
Другие вопросы по тегам