1

I have two matrices (tri1 and tri2) which represent a Delaunay triangulation. tri1 is the triangulation before inserting a new point, tri2 is the result after adding a new point. Each row has 4 columns. The rows represent tetrahedra.

I would like to calculate a relation between lines from tri1 to tri2. A result could look like this:

result =

 1     1
 2     2
 3     3
 4     4
 0     0 % tri1(5, :) was not found in tri2 (a lot more lines could be missing)
 6     5
 7     6
 8     7
 9     8
10     9

Currently my source code looks like this:

% sort the arrays
[~, idx1] = sort(tri1(:, 1), 'ascend');
[~, idx2] = sort(tri2(:, 1), 'ascend');

stri1 = tri1(idx1, :);
stri2 = tri2(idx2, :);

result = zeros(size(tri1, 1), 2);

% find old cells in new triangulation
deleted = 0;
for ii = 1:size(tri1, 1)
    found = false;
    for jj = ii-deleted:size(tri2, 1)
        if sum(stri1(ii, :) == stri2(jj, :)) == 4 % hot spot according to the profiler
            found = true;
            break;
        end
        if (stri1(ii, 1) < stri2(jj, 1)), break, end;
    end
    if found == false
        deleted = deleted + 1;
    else
        result(idx1(ii), 1) = idx1(ii);
        result(idx1(ii), 2) = idx2(jj);
    end
end

The above source code gives me the results that I want, but not fast enough. I am not very experienced with MATLAB, I usually work with C++. My question: How can I speed up the comparison of two rows?

Some additional information (just in case):

  • the number of rows in tri can grow to about 10000
  • this function will be called once per inserted vertex (about 1000)
4

1 回答 1

3

I cannot follow your example code completely, but judging from your explanation you want to see whether a row from matrix A occurs in matrix B.

In this case a very efficient implentation is available:

[Lia, Locb] = ismember(A,B,'rows');

Check the doc for more information about this function and see whether it is what you need.

于 2013-10-23T13:08:36.290 回答