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:
Barycentric Subdivision

Subject: Barycentric Subdivision

From: Owen

Date: 13 Mar, 2009 20:14:01

Message: 1 of 4

Hi there.
I want to write an M-file which will output a diagram showing the n-th Barycentric Subdivision (BCS) of the unit triangle in R^2.

By the n-th BCS I mean: divide the triangle into its BCS. Then divide all the sub-triangles in the triangulation by their own BCS.

The following may be helpful if unfamiliar with BCS,

wikipedia entry -
http://en.wikipedia.org/wiki/Barycentric_subdivision

diagram of the divisions for n = 1,2,3,4 -
http://www.math.vt.edu/people/floyd/coloring/barycent.pdf

If anybody has already written an M-file that achieves this I would be interested in seeing it, or if anyone has any tips on how to get started this would also be of great help.

Thank you.

Owen.

PS. I am fairly inexperienced with Matlab, and most experience I have had has been in Numerical analysis areas, as opposed to constructing such algorithms.

Subject: Barycentric Subdivision

From: Roger Stafford

Date: 14 Mar, 2009 01:21:01

Message: 2 of 4

"Owen " <owen.daniel@removethis.warwick.ac.uk> wrote in message <gpeeq9$e07$1@fred.mathworks.com>...
> Hi there.
> I want to write an M-file which will output a diagram showing the n-th Barycentric Subdivision (BCS) of the unit triangle in R^2.
>
> By the n-th BCS I mean: divide the triangle into its BCS. Then divide all the sub-triangles in the triangulation by their own BCS.
>
> The following may be helpful if unfamiliar with BCS,
>
> wikipedia entry -
> http://en.wikipedia.org/wiki/Barycentric_subdivision
>
> diagram of the divisions for n = 1,2,3,4 -
> http://www.math.vt.edu/people/floyd/coloring/barycent.pdf
> .......

  The figures in "barycent.pdf" do not look like true barycentric subdivisions to me, from n = 2 case on. In the Wikipedia reference you also gave, they state: "The BCS of a triangle S divides it into six triangles; each part has one vertex v2 at the barycenter of S, another one v1 at the midpoint of some side, and the last one v0 at one of the original vertices." The figures shown in "barycent.pdf" do not divide the triangle sides at their midpoints nor do they meet at the barycenter - far from it! At n = 4 each side of the original triangle ought to have been divided into 16 equal segments and that certainly isn't true of the figure shown for the 4th BCS.

  On the possibility that these pdf figures do not represent what you actually want, here is some code that plots the n-th barycentric subdivision of the original triangle, as I understand the concept.

 n = 4; % <-- Set n to the desired depth of subdivision
 M = [1/2,-sqrt(3)/6,0,sqrt(3)/3,-1/2,-sqrt(3)/6]; % First triangle
 for k = 1:n
  t1 = M(:,1:2); t2 = M(:,3:4); t3 = M(:,5:6);
  t12 = [(M(:,1)+M(:,3))/2,(M(:,2)+M(:,4))/2];
  t23 = [(M(:,3)+M(:,5))/2,(M(:,4)+M(:,6))/2];
  t31 = [(M(:,5)+M(:,1))/2,(M(:,6)+M(:,2))/2];
  t123 = [(M(:,1)+M(:,3)+M(:,5))/3,(M(:,2)+M(:,4)+M(:,6))/3];
  M = [t123,t1,t12;t123,t12,t2;t123,t2,t23; ...
       t123,t23,t3;t123,t3,t31;t123,t31,t1];
 end
 m = size(M,1);
 hold on
 for k = 1:m
  plot(M(k,[1 3 5 1]),M(k,[2 4 6 2]),'y-')
 end
 axis equal
 hold off

  M will be an m x 6 array in which each row represents the three vertices of a subdivision triangle, the first two elements, the second two, and the third two being the x and y pair of coordinates of the respective vertices. For the n = 4 case there should be m = 1296 rows in M.

Roger Stafford

Subject: Barycentric Subdivision

From: Owen

Date: 14 Mar, 2009 10:36:01

Message: 3 of 4

Roger.

Thank you for your message, and in particular for the code.

What you say is true: I had noticed that the pdf does not create exactly the n-th BCS... I noticed this a rather laborious way since when originally thinking about this problem I actually did drawings of the first three! Its fairly evident as soon as you do the second that the images are different. I chose to include the .pdf however since I thought it gave a representation of 'roughly' what was desired... I should have made this observation clearer myself.

Once again, thank you for the code.

Owen.
 

Subject: Barycentric Subdivision

From: Roger Stafford

Date: 15 Mar, 2009 03:00:04

Message: 4 of 4

"Owen " <owen.daniel@removethis.warwick.ac.uk> wrote in message <gpg1ah$c8i$1@fred.mathworks.com>...
> ......
> What you say is true: I had noticed that the pdf does not create exactly the n-th BCS... I noticed this a rather laborious way since when originally thinking about this problem I actually did drawings of the first three! Its fairly evident as soon as you do the second that the images are different.
> ......

  I noticed that the pdf apparently used a triangle's "incenter" - that is, the intersection of its angle bisectors - in place of its true barycenter. However I am unable to determine how the three lines drawn from the incenter to the triangle sides are selected. They aren't angle bisectors nor are they orthogonal lines from the incenter.

Roger Stafford

Tags for 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