Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
How to "propagate" around Delaunay triangulation

Subject: How to "propagate" around Delaunay triangulation

From: LeviCivita

Date: 31 Mar, 2012 19:54:11

Message: 1 of 3

Hey,

I'm trying to solve a problem and am stuck with a necessary step. I'm given Delaunay triangulation, i.e. I have a vector with n rows and three columns. Each row specifies a triangle. For example:

1 3 4
2 4 7
1 6 9

means that the first triangle connects dots 1,3 and 4, the second one connects 2,4 and 7. And so on.

Here is the problem:

I want to SORT this vector with respect to ROWS (in other words change the order of triangles) so that, after first triangle, let's say we fix it to be 1 3 4, the ones that follow it are such that they have TWO VERTICES in common with AT LEAST one triangle above them.

For example,

1 3 4
1 5 8
3 6 4
6 4 2

would be ordered, for example, like this

1 3 4 (fixed)
3 6 4
6 4 2
1 5 8.

I tried lots of thing, but it seems I don't have a good idea in mind.

Could you please help me? Is there a function that can be of use?

Thanks a lot.

Subject: How to "propagate" around Delaunay triangulation

From: Roger Stafford

Date: 1 Apr, 2012 06:21:23

Message: 2 of 3

"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

Subject: How to "propagate" around Delaunay triangulation

From: Steven_Lord

Date: 2 Apr, 2012 01:23:07

Message: 3 of 3



"LeviCivita " <zlatni.rez@gmail.com> wrote in message
news:jl7nd3$mnm$1@newscl01ah.mathworks.com...
> Hey,
>
> I'm trying to solve a problem and am stuck with a necessary step. I'm
> given Delaunay triangulation, i.e. I have a vector with n rows and three
> columns. Each row specifies a triangle. For example:
>
> 1 3 4
> 2 4 7
> 1 6 9
>
> means that the first triangle connects dots 1,3 and 4, the second one
> connects 2,4 and 7. And so on.
>
> Here is the problem:
>
> I want to SORT this vector with respect to ROWS (in other words change the
> order of triangles) so that, after first triangle, let's say we fix it to
> be 1 3 4, the ones that follow it are such that they have TWO VERTICES in
> common with AT LEAST one triangle above them.

Take a look at the DelaunayTri object's edgeAttachment or neighbors methods.

http://www.mathworks.com/help/techdoc/ref/delaunaytriclass.html

--
Steve Lord
slord@mathworks.com
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us