如何从3D Delaunay三角剖分中获取三角形

Question

我有一个三维点云的三角剖分dt（或者可能是四面体剖分），我想找到一种好的方法从中提取三角形。注意，我知道如何获取四面体，只需使用dt.ConnectivityList即可，是否有一种有效的方法从四面体中获取三角形？列表中每个三角形应仅出现一次。

目前我正在执行以下操作-但它非常缓慢：

dt = delaunayTriangulation([X Y Z]);
tetrahedra = dt.ConnectivityList;

tris = cell(1, size(tetrahedra, 1)); % contains indices of tris in a tetra
for tt=1:size(tetrahedra, 1)
    vertIds = tetrahedra(tt, :); % vertex indices

    vmask = logical([0 1 1 1]);
    tris{tt} = [vertIds(circshift(vmask, [0 0 0 0]));
                vertIds(circshift(vmask, [1 1 1 1]));
                vertIds(circshift(vmask, [2 2 2 2]));
                vertIds(circshift(vmask, [3 3 3 3]))];
end

tris = unique(sort(cell2mat(tris'), 2), 'rows');

- brtk

---

我并没有查看你在那里使用的任何函数，但是你是否尝试将 tris 声明为数组而不是单元数组？在大循环中使用单元格会有一些“有趣”的经历。 - McMa

@McMa 是的，那是一种可能的优化方法，但我仍然需要对每行进行排序，然后删除重复项。 - brtk

Answer 1

这里是向量化版本：

% take all four subsets of three points from the tets and concatenate
tris2 = [tetrahedra(:,[1 2 3]); tetrahedra(:,[1 2 4]); tetrahedra(:,[1 3 4]); tetrahedra(:, [2 3 4])];
% sort each row
tris2 = sort(tris2, 2);
% eliminate duplicates
tris2 = unique(tris2, 'rows');

使用10万个测试点（随机数字），我得到了以下结果：

Cellmethod: time=9.870982, numelements = 1344960
Vectmethod: time=1.014797, numelements = 1344960

- xenoclast

---

我知道对于你的申请来说可能已经太晚了，但是我喜欢这个谜题... - xenoclast