如何从 MATLAB 中的现有三角剖分创建 delaunayTriangulation 对象

Question

我有一个现有的三角剖分（顶点 x 和 y 以及连接矩阵 tri），我想应用 [=14] 的 PointLocation 方法=] class 在这个现有的三角剖分上（很像旧版本 MATLAB 中过时的 tsearch 函数）。

然而，PointLocation 方法显然需要一个 delaunayTriangulation 实例作为输入。给定顶点 x 和 y.

有没有办法将 PointLocation（或 tsearch 之类的东西）应用于我现有的三角剖分？我有 Matlab 2013a.

Answer 1

将 triangulation 变成 delaunayTriangulation:

当然不可能对所有 triangulation 而言，因为它们不满足 Delaunay 属性。
如果您的 trep 表现良好，则约束 Delaunay 三角剖分可能有效，但可能会添加额外的三角形和洗牌节点： delaunayTriangulation(trep.Points, trep.edges);

因此，我向您提出以下建议

解决方法：

您可以使用 triangulation class:

中的方法构建解决方法

trep = triangulation(tri, x, y);
QPs = rand(10,2); % Query points.
TI = pointLocation(trep, QPs);

使用自制软件功能pointLocation:

function TI = pointLocation(trep, QPs)
% Find query point QPs in triangulation trep
TI = cell(size(QPs,1), 1);
for i = 1:size(QPs,1)
    barys = trep.cartesianToBarycentric((1:size(trep,1))', repmat(QPs(i,:),size(trep,1),1));
    TI{i} = find(all((0<=barys)&(barys<=1),2));
end

请注意，TI 是一个元胞数组，至于三角剖分，不能确定它们在某种意义上是规则的，因为只有一个 triangle/tetrahedron 包含该点。其工作方式是计算查询点相对于所有 triangles/tetrahedra 的重心坐标，然后使用这些坐标来检查这些点是否确实在它们内部。（如果所有重心坐标都在0<=bx,by,bz<=1以内就是这种情况。）

Answer 2

我认为没有一种简单的方法可以让 MATLAB 的内置三角测量例程为您执行此操作——正如您所指出的，它们明确要求三角测量是 Delaunay...

不过，您可能有兴趣查看我的 FINDTRIA routines（可从 MATLAB 文件交换获得）。 FINDTRIA 是一个工具箱，旨在对任意（d 维）三角剖分执行点定位查询，包括那些非 Delaunay、非凸甚至重叠的三角剖分，因此它应该按原样处理您的三角剖分。

虽然不如 MATLAB 的内置 pointLocation 例程那么快（当底层三角剖分是 Delaunay 时），FINDTRIA 通常比蛮力更有效 O(n*m) 搜索每个 point/triangle 对。 FINDTRIA 利用几何搜索树 -- an AABB-tree -- 来加速计算。

从 R2014b 开始，MATLAB 也支持使用 pointLocation 例程查询非 Delaunay 三角剖分，尽管我的初步经验似乎表明这个新的内置函数可能相当不错当三角剖分不是 Delaunay 时慢...

如何从 MATLAB 中的现有三角剖分创建 delaunayTriangulation 对象

How to create a delaunayTriangulation object from an existing triangulation in MATLAB

matlab

delaunay

triangulation

解决方法：