TL; DR:我有一堆四面体,我想知道它的4个(或更少)相邻(面部共享)四面体是什么,我通过检查它们共享的3D点来做到这一点。这很慢。
我正在从三角测量中构建连通图。该图的结构为[1]:
Graph.element.nodeId
.neighbours
.nodes.positions
并且三角测量的输出有2个矩阵,TRI
和points
,第一个是Ntri x 4
数组,在每一行中具有每个四面体的节点Ids,而secodn one是点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);
如何提高此代码的性能?我期待它需要一种不同的方法,而不仅仅是更快的命令。我看了一下voronoi图,但似乎无论如何都需要完成这个发现(find
)。
注意:我不一定需要MATLAB代码,如果你知道解决问题的算法请回答,我将在MATLAB中编写代码。
[1]是的,最好将此信息存储在一维数组中。我会稍后,但现在的结构更容易理解。
啊,当然有一个内置的
如果使用delaunay()
而不是具有自己类的较新版本,那就行了
neighbors(triangulation(TRI,points))
为了得到邻居。边界元素将具有NaN以填充矩阵。