Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: How to "propagate" around Delaunay triangulation
Date: Sun, 1 Apr 2012 06:21:23 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 42
Message-ID: <jl8s53$nqo$1@newscl01ah.mathworks.com>
References: <jl7nd3$mnm$1@newscl01ah.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: www-06-blr.mathworks.com
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: newscl01ah.mathworks.com 1333261283 24408 172.30.248.38 (1 Apr 2012 06:21:23 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Sun, 1 Apr 2012 06:21:23 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:762831

"LeviCivita" wrote in message <jl7nd3$mnm$1@newscl01ah.mathworks.com>...
> ....... I'm given Delaunay triangulation, i.e. I have a vector with n rows and three columns. Each row specifies a triangle.
> .......
> I want to SORT this vector with respect to ROWS (in other words change the order of triangles) so that, after first triangle ..... the ones that follow it are such that they have TWO VERTICES in common with AT LEAST one triangle above them.
- - - - - - - - - -
  It is comparatively easy to devise an algorithm that adds triangles one at a time to a list which have a common edge with a triangle already in the list by searching linearly each time through those not yet on the list.  Unfortunately it would have an order(n^2) complexity and for large n it would therefore be slow,

  If speed of execution is important to you, you might consider using a pair of 'unique' calls with the 'rows' option.  This will serve to give you an order(n*log(n)) algorithm which for large n should be faster.

  The basic assumption is made here that every triangle edge in your triangulation occurs either once on a periphery or twice in the interior, and that the entire covered region is "connected" in the sense of connection across common edges.

  Let A be your three-columned triangulation matrix of vertex indices.  Then do the following:

B = sort(A.',1);
B = reshape(B([1,2,1,3,2,3],:),2,[]).';
[~,m1,n] = unique(B,'rows','first');
[~,m2]   = unique(B,'rows','last' );
N = size(B,1);
p = [1;2;3;zeros(N-3,1)];
f = [true(3,1);false(N-3,1)];
i1 = 0;
i2 = 3;
while i1 < i2
  i1 = i1 + 1;
  s = n(p(i1));
  t = m1(s);
  if f(t)
    t = m2(s);
  end
  if ~f(t)
    u = 3*ceil(t/3) + (-2:0);
    i2 = i2 + 3;
    p(i2-2:i2) = u;
    f(u) = true;
  end
end
B = reshape(B(p(1:i2),:).',6,[]);
B = B([1,2,4],:).';

In B the triangles have been reordered in such a way that every triangle except the top one shares an edge with one above it.  Naturally A and B would be the same size (provided the "connected" assumption above is true.)  (Note that the vertex indices in each triangle have been rearranged in ascending order to make 'unique/rows' work properly.)

Roger Stafford