Converting TriRep to DelaunayTri while using pointLocation?

hi, I have a TriRep object with triangulations and I want to use pointLocation on the object to find whether the points are inside the triangles. But the pointLocation is a method defined for DelaunayTri class which is a subclass of TriRep. So I would like to ask if TriRep object can be converted to DelaunayTri to be used in pointLocation?

Answer 1

[Divyam]

Hi @Arpan,

The "DelaunayTri " object can be created using the extracted points from the "TriRep" object. As of MATLAB R2024b, "DelaunayTri " class is not recommended for usage and it's preferable to use the "delaunayTriangulation" class instead.

% Assume T is your TriRep object
T = TriRep([1, 2, 3; 1, 3, 4], [0, 0; 1, 0; 0, 1; 1, 1]);

% Extract the points
points = T.X;

% Create a DelaunayTri object
delaunayTriObj = DelaunayTri(points);

% Define points to check
P = [0.5, 0.5; 0.75, 0.75; 0.25, 0.25];

% Use pointLocation to find the triangles containing the points
triangleIndices = pointLocation(delaunayTriObj, P);

% Display the results
fprintf('Triangle indices for the query points: [%s]\n', join(string(triangleIndices),','));

Triangle indices for the query points: [2,2,1]

For more information regarding the "delaunayTriangulation" class, refer to the following documentation: https://www.mathworks.com/help/matlab/ref/delaunaytriangulation.html

[DGM]

This completely discards the original triangulation, so there's no way to test if a point is inside a particular triangle/tetra, since all the original ones are gone.

% this isn't a valid triangulation anyway
% two overlapping triangles (non-convex)
T = TriRep([1 2 3; 1 3 4], [0 0; 1 0; 0 1; 1 1]);

% create a DT of the convex hull of the original points
DT = DelaunayTri(T.X);

% these do not reference the triangles of object T
P = [0.5 0.25; 0.5 0.75; 0.25 0.5];
Tidx = pointLocation(DT,P)

Tidx = 3×1

1 2 1

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

plotthings(T,DT,P)

Obviously, we can't represent the original triangles. Without a constraint list, we can't even represent the original shape unless it's both convex and 2D.

Try the same thing with a valid triangulation. The problem is the same. We can't represent the non-convex geometry, and even if we could, we don't get to control how the interior of the shape gets retriangulated. In terms of our original triangles, the indices we get are meaningless.

% start with something that is valid
% two non-overlapping trianges (non-convex)
T = TriRep([1 5 3; 2 4 5], [0 0; 1 0; 0 1; 1 1; 0.5 0.5]);

% create a DT of the convex hull of the original points
DT = DelaunayTri(T.X);

% these do not reference the triangles of object T
P = [0.5 0.25; 0.5 0.75; 0.25 0.5];
Tidx = pointLocation(DT,P)

Tidx = 3×1

4 2 1

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

●

plotthings(T,DT,P)

% this isn't important.  it's just plotting things.
function plotthings(T,DT,P)
    figure
    subplot(1,2,1)
    [F V] = t2fv(T);
    patch('faces',F,'vertices',V,'facecolor',[1 1 1]*0.8,'edgecolor','k');
    axis equal; grid on; hold on
    plot(P(:,1),P(:,2),'.','markersize',10)
    % use a colored border in order to make it clear 
    % when triangles are overlapping (example 1)
    for k = 1:size(F,1)
        plot(V(F(k,[1 2 3 1]),1),V(F(k,[1 2 3 1]),2),'-','linewidth',2)
    end
    
    subplot(1,2,2)
    [F V] = t2fv(DT);
    patch('faces',F,'vertices',V,'facecolor',[1 1 1]*0.8,'edgecolor','k');
    axis equal; grid on; hold on
    plot(P(:,1),P(:,2),'.','markersize',10)
    for k = 1:size(F,1)
        plot(V(F(k,[1 2 3 1]),1),V(F(k,[1 2 3 1]),2),'-','linewidth',2)
    end
end

Answer 2

[DGM]

You can't build a DelaunayTri or delaunayTriangulation object from a TriRep or triangulation object without performing a retriangulation. If the boundary is non-convex, then that adds extra complications.