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:
Forcing Delaunay triangulation to have a symmetric behaviour

Subject: Forcing Delaunay triangulation to have a symmetric behaviour

From: Kenan

Date: 24 Apr, 2013 23:10:10

Message: 1 of 5

Hello all,

I am using Delaunay triangulation to split polygons into triangles. I work on FEM with a very large code, and one of my "checkpoints" is symmetry (if the data is symmetric, the output has to be symmetric too). However, since I have no control over the Delaunay triangulation, it makes me loose the symmetry.

I have written a small code that illustrates my problem: we consider two disjoints triangles and a big rectangle that intersects them. We want to triangulate the intersections and subtractions of those triangles with the rectangle:

"
clear all
close all
warning off % the warning is about duplicate points, not important here

figure
hold on

p =[.3 .3
    .4 .3
    .3 .4
    .7 .6
    .6 .7
    .7 .7]; % coordinates of the points for the triangles

px = 1/3;
py = 1/3;
lx = 1/3;
ly = 1/3; % size and position of the rectangle

% rearrange the polygon with clockwise-ordered vertices
[x1,y1]=poly2cw([px; px+lx; px+lx; px],[py; py; py+ly; py+ly]); % rectangle

patch(x1,y1, 1, 'EdgeColor', 'k');

for i=1:2
    
    pc = p(3*i-2:3*i,:); % current triangle
    % rearrange the polygon with clockwise-ordered vertices
    [x0,y0]=poly2cw(pc(:,1),pc(:,2)); % triangle
    
    [x2,y2] = polybool('intersection',x1,y1,x0,y0); % intersection
    [x3,y3] = polybool('subtraction',x0,y0,x2,y2); % subtraction
    
    DT = delaunayTriangulation(x3,y3);
    
    triplot(DT)
    
end
"

As you can see, the Delaunay triangulation does not have the same behaviour in both triangles, hence the loss of symmetry.

Is there a simple way to recover symmetry?

Thank you.

Kenan

Subject: Forcing Delaunay triangulation to have a symmetric behaviour

From: Bruno Luong

Date: 24 Apr, 2013 23:43:09

Message: 2 of 5

"Kenan" wrote in message <kl9ooi$hcp$1@newscl01ah.mathworks.com>...

> Is there a simple way to recover symmetry?
>

mesh the half then flip?

Or the way people usually do: solve the symmetric problem on the half domain.

Bruno

Subject: Forcing Delaunay triangulation to have a symmetric behaviour

From: Kenan

Date: 25 Apr, 2013 04:07:07

Message: 3 of 5

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kl9qmc$m36$1@newscl01ah.mathworks.com>...
> "Kenan" wrote in message <kl9ooi$hcp$1@newscl01ah.mathworks.com>...
>
> > Is there a simple way to recover symmetry?
> >
>
> mesh the half then flip?
>
> Or the way people usually do: solve the symmetric problem on the half domain.
>
> Bruno

Thank you for your help Bruno.
Actually, this is only a way to check whether my problem (in the general case not symmetric) is correctly solved. So what you suggested is not what I want.

Subject: Forcing Delaunay triangulation to have a symmetric behaviour

From: Kenan

Date: 25 Apr, 2013 20:52:08

Message: 4 of 5

See here for other details and images:
http://stackoverflow.com/questions/16203815/delaunay-triangulation-makes-me-lose-symmetry

Subject: Forcing Delaunay triangulation to have a symmetric behaviour

From: Kenan

Date: 5 May, 2013 02:44:10

Message: 5 of 5

I had an 'official' asnwser from the technical support:

"This is definitely due to sensitivity to small rounding differences.
To see the effect, run the attached, modified script several times and observe that
the results are different every time.
It adds very small random errors(magnitude ~1e-12) to the vertices of your polygon defined by x3,y3.

I can only agree with the stackoverflow answer:
"You have to redesign your points in order to get reliable result which does not depend on such things."

Basically, you cannot depend on delaunay triangulation preserving this kind of symmetry."

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