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:
DelaunayTri efficiency

Subject: DelaunayTri efficiency

From: R Wat

Date: 30 May, 2013 19:48:09

Message: 1 of 4

I have recently been working with Delaunay triangulation and was surprised at how long the triangulation procedure was taking. In total, my data has around 100,000 points in a relatively nicely spaced grid, which is large, but doesn't seem to be outrageous. In my tinkering around with things, I came across an interesting finding which is demonstrated in the following code:

% Random grid of points
X1 = rand(300*300,2);

% Equally spaced, well ordered, grid (of the same size as the above random data)
[x,y] = meshgrid(1:300,1:300);
X2 = [x(:),y(:)];

% Triangulate the random data and calculate the run time
tic;
random = DelaunayTri(X1);
toc;

% Triangulate the well ordered data
tic;
ordered = DelaunayTri(X2);
toc;

% Take the well ordered grid data and scramble it so that it is no longer well ordered
scramble = randperm(numel(x)).';
X3 = [x(scramble),y(scramble)];

% Triangulate the now scrambled data
tic;
scrambled = DelaunayTri(X3);
toc;

Which gives the following output for the timing:
Elapsed time is 1.037137 seconds. (Random data)
Elapsed time is 10.460786 seconds. (Grid data)
Elapsed time is 0.900113 seconds. (Scrambled grid data)

What confuses me is that for the first two cases, triangulation of the same number of points takes a drastically different amount of time (10x slower). What is even more confusing is that, when you scramble the order of the grid data, the performance drops back to that of the random data.

Does anybody know why this occurs? I kind of have a guess, but it is hind of "hand wavy."

Subject: DelaunayTri efficiency

From: Gold APP Instruments Andy

Date: 31 May, 2013 02:46:17

Message: 2 of 4

"R Wat" wrote in message <ko8adp$p8r$1@newscl01ah.mathworks.com>...
> I have recently been working with Delaunay triangulation and was surprised at how long the triangulation procedure was taking. In total, my data has around 100,000 points in a relatively nicely spaced grid, which is large, but doesn't seem to be outrageous. In my tinkering around with things, I came across an interesting finding which is demonstrated in the following code:
>
> % Random grid of points
> X1 = rand(300*300,2);
>
> % Equally spaced, well ordered, grid (of the same size as the above random data)
> [x,y] = meshgrid(1:300,1:300);
> X2 = [x(:),y(:)];
>
> % Triangulate the random data and calculate the run time
> tic;
> random = DelaunayTri(X1);
> toc;
>
> % Triangulate the well ordered data
> tic;
> ordered = DelaunayTri(X2);
> toc;
>
> % Take the well ordered grid data and scramble it so that it is no longer well ordered
> scramble = randperm(numel(x)).';
> X3 = [x(scramble),y(scramble)];
>
> % Triangulate the now scrambled data
> tic;
> scrambled = DelaunayTri(X3);
> toc;
>
> Which gives the following output for the timing:
> Elapsed time is 1.037137 seconds. (Random data)
> Elapsed time is 10.460786 seconds. (Grid data)
> Elapsed time is 0.900113 seconds. (Scrambled grid data)
>
> What confuses me is that for the first two cases, triangulation of the same number of points takes a drastically different amount of time (10x slower). What is even more confusing is that, when you scramble the order of the grid data, the performance drops back to that of the random data.
>
> Does anybody know why this occurs? I kind of have a guess, but it is hind of "hand wavy."
==================================================
Gold APP Instruments Corporation China, the leader, specializes in BET surface analyser, surface area and pore size analyzer, gas pycnometer true density analyzer and high pressure gas sorption analyzer manufacturing for laboratories, institutes and manufacturers.

Dealers, distributors, agents, wholesalers are recruiting currently. If you interest pls let us know.

Gold APP Instruments Corp. China
Web: www.jinaipu.com/ www.app-one.com.cn
Tel.: 0086-10-82133318 Ext.810
Fax: 0086-10-82118197
Mobile: 0086-18210009838
IMs:
MSN: goldapp@msn.com
Skype: Gold-APP-Instruments
Yahoo: goldappinstruments@ymail.com
Gtalk: goldappinstruments2008@gmail.com

We can provide materials for tender or bid/binding documents, such as authorization letter, technology compliance data sheet, also can offer some experiences in invitation for bids, bid security form, checklist, submission of bids, technical bid, price schedule, performance security, commercial bid and so on.

Subject: DelaunayTri efficiency

From: Eric Sampson

Date: 31 May, 2013 16:54:13

Message: 3 of 4

"R Wat" wrote in message <ko8adp$p8r$1@newscl01ah.mathworks.com>...
> I have recently been working with Delaunay triangulation and was surprised at how long the triangulation procedure was taking. In total, my data has around 100,000 points in a relatively nicely spaced grid, which is large, but doesn't seem to be outrageous. In my tinkering around with things, I came across an interesting finding which is demonstrated in the following code:
>
> % Random grid of points
> X1 = rand(300*300,2);
>
> % Equally spaced, well ordered, grid (of the same size as the above random data)
> [x,y] = meshgrid(1:300,1:300);
> X2 = [x(:),y(:)];
>
> % Triangulate the random data and calculate the run time
> tic;
> random = DelaunayTri(X1);
> toc;
>
> % Triangulate the well ordered data
> tic;
> ordered = DelaunayTri(X2);
> toc;
>
> % Take the well ordered grid data and scramble it so that it is no longer well ordered
> scramble = randperm(numel(x)).';
> X3 = [x(scramble),y(scramble)];
>
> % Triangulate the now scrambled data
> tic;
> scrambled = DelaunayTri(X3);
> toc;
>
> Which gives the following output for the timing:
> Elapsed time is 1.037137 seconds. (Random data)
> Elapsed time is 10.460786 seconds. (Grid data)
> Elapsed time is 0.900113 seconds. (Scrambled grid data)
>
> What confuses me is that for the first two cases, triangulation of the same number of points takes a drastically different amount of time (10x slower). What is even more confusing is that, when you scramble the order of the grid data, the performance drops back to that of the random data.
>
> Does anybody know why this occurs? I kind of have a guess, but it is hind of "hand wavy."

What version of MATLAB are you using? I seem to recall that they fixed this a while ago. I can't replicate it in my version of R2013a on Win7 x64, at least. The timing in the first two cases is pretty much the same.

Subject: DelaunayTri efficiency

From: R Wat

Date: 31 May, 2013 17:15:10

Message: 4 of 4

"Eric Sampson" wrote in message <koakjl$rf6$1@newscl01ah.mathworks.com>...
> "R Wat" wrote in message <ko8adp$p8r$1@newscl01ah.mathworks.com>...
> > I have recently been working with Delaunay triangulation and was surprised at how long the triangulation procedure was taking. In total, my data has around 100,000 points in a relatively nicely spaced grid, which is large, but doesn't seem to be outrageous. In my tinkering around with things, I came across an interesting finding which is demonstrated in the following code:
> >
> > % Random grid of points
> > X1 = rand(300*300,2);
> >
> > % Equally spaced, well ordered, grid (of the same size as the above random data)
> > [x,y] = meshgrid(1:300,1:300);
> > X2 = [x(:),y(:)];
> >
> > % Triangulate the random data and calculate the run time
> > tic;
> > random = DelaunayTri(X1);
> > toc;
> >
> > % Triangulate the well ordered data
> > tic;
> > ordered = DelaunayTri(X2);
> > toc;
> >
> > % Take the well ordered grid data and scramble it so that it is no longer well ordered
> > scramble = randperm(numel(x)).';
> > X3 = [x(scramble),y(scramble)];
> >
> > % Triangulate the now scrambled data
> > tic;
> > scrambled = DelaunayTri(X3);
> > toc;
> >
> > Which gives the following output for the timing:
> > Elapsed time is 1.037137 seconds. (Random data)
> > Elapsed time is 10.460786 seconds. (Grid data)
> > Elapsed time is 0.900113 seconds. (Scrambled grid data)
> >
> > What confuses me is that for the first two cases, triangulation of the same number of points takes a drastically different amount of time (10x slower). What is even more confusing is that, when you scramble the order of the grid data, the performance drops back to that of the random data.
> >
> > Does anybody know why this occurs? I kind of have a guess, but it is hind of "hand wavy."
>
> What version of MATLAB are you using? I seem to recall that they fixed this a while ago. I can't replicate it in my version of R2013a on Win7 x64, at least. The timing in the first two cases is pretty much the same.

I am using version R2009b on Mac OSX x64. I just ran my demo on a R2012a (Win7 x64) and produced consistent timing for all three cases. So, I guess the bug was fixed sometime in between R2009b and R2012a.

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