Построение связного графа из триангуляции - PullRequest
Новая
       46

Построение связного графа из триангуляции

0 голосов
/ 07 сентября 2018

TL; DR: У меня есть несколько тетраэдров, и я хочу знать, какие из них 4 (или меньше) соседних (разделяющих лица) тетраэдров, и я делаю это, проверяя точки в 3D, которые они делят. Это медленно.

Я строю связный граф из триангуляции. Граф имеет структуру как [1]: 

Graph.element.nodeId
             .neighbours
     .nodes.positions

И выходные данные триангуляции имеют 2 матрицы, TRI и points, первая из которых является массивом Ntri x 4, в каждой строке есть идентификаторы узлов для каждого тетраэдра, а второй - список точка Npoint x 3 размер.

В настоящее время я строю график, как в приведенном ниже коде, но он абсурдно медленен для любого приличного размера сетки. Единственная строка, которая занимает почти все время, - это строка find (отмечена в коде), часть, в которой находятся соседи текущего элемента.

Текущий алгоритм берет для каждого тетраэдра все его узлы, а затем находит все остальные тетраэдры, которые также содержат эти же узлы. Затем он отфильтровывает все тетраэдры, которые не содержат 3 тех же узлов, что и текущий, оставляя только соседей текущего тетраэдра. 

function graph=trimesh2graph(TRI,points)
nD=size(points,2);
% preallocate.
graph.elements(size(TRI,1)).neighbours=[];


% For each element, find its node Ids and neighbouring elements
for ii=1:size(TRI,1)
    nodeids=TRI(ii,:);
    elem=[];
    for jj=1:(nD+1)
        [iind,~]=find(nodeids(jj)==TRI); % this is 80% of the time
        elem=[elem; iind];
    end
    u = unique(elem);

    % of all elements that have shared nodes with the current element, 
    % get only the ones that have 3 shared nodes.
    graph.elements(ii).neighbours = int32((u(histc(elem,u)==nD)));


   % some other code
end
% some other code

Запустите этот скрипт с демонстрационными данными: 

x = gallery('uniformdata',[30 1],0);
y = gallery('uniformdata',[30 1],1);
z = gallery('uniformdata',[30 1],2);
vertices=[x,y,z];
TRI= delaunay(x,y,z)
trimesh2graph(TRI,vertices);

Как я могу улучшить производительность этого кода? Я ожидаю, что это потребует другого подхода, а не просто более быстрых команд. Я немного посмотрел на вороной диаграммы, но, похоже, что в любом случае (find) нужно сделать.

Примечание: мне не обязательно нужен код MATLAB. Если вам известен алгоритм решения проблемы, ответьте, я напишу его в MATLAB.

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

1 Ответ

0 голосов
/ 07 сентября 2018

Ах, конечно, есть встроенный для этого

если используется delaunay() вместо более новой версии с собственным классом, просто наберите 

neighbors(triangulation(TRI,points))

Чтобы получить соседей. Граничные элементы будут иметь NaN для заполнения матрицы.

...