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:
alternative to delaunayn

Subject: alternative to delaunayn

From: Jveer

Date: 8 Oct, 2009 20:43:03

Message: 1 of 9

as most of you probably already know the in built 'delaunayn' function is way too also for realistic practical applications.

does anyone know of any alternatives with the same functionality?

how about creating a c mex version of it?

Subject: alternative to delaunayn

From: Jveer

Date: 8 Oct, 2009 21:16:13

Message: 2 of 9

i meant * way too SLOW

Subject: alternative to delaunayn

From: Rune Allnor

Date: 8 Oct, 2009 22:20:31

Message: 3 of 9

On 8 Okt, 23:16, "Jveer " <jv...@jveer.com> wrote:
> i meant * way too SLOW

Two comments:

1) Higher-dimensional geometric algorithms *are* slow. Don't be
   surprised if the complexity goes something like O(f(N)^k)
   where k is the number of dimensions. With a bit of luck,
   f(N) < N, but don't rely on it.
2) For non-specific number of dimensions, a lot os stuff that
   could have been optimized by a compiler, has to remain
   non-optimized. If you have a specific application in mind,
   write a special purpose application that is optimized
   for that problem.

Rune

Subject: alternative to delaunayn

From: Jveer

Date: 9 Oct, 2009 01:20:18

Message: 4 of 9

Rune Allnor <allnor@tele.ntnu.no> wrote in message <b636c673-7327-4e75-8243-64ffe57f3301@f10g2000vbf.googlegroups.com>...
> On 8 Okt, 23:16, "Jveer " <jv...@jveer.com> wrote:
> > i meant * way too SLOW
>
> Two comments:
>
> 1) Higher-dimensional geometric algorithms *are* slow. Don't be
> surprised if the complexity goes something like O(f(N)^k)
> where k is the number of dimensions. With a bit of luck,
> f(N) < N, but don't rely on it.
> 2) For non-specific number of dimensions, a lot os stuff that
> could have been optimized by a compiler, has to remain
> non-optimized. If you have a specific application in mind,
> write a special purpose application that is optimized
> for that problem.
>
> Rune

thanks for the reply Rune.

this is how i use it : tetr=delaunayn(P',{'QJ'}) where P is a 3Xn matrix. n is usually very large.

delaunay3 is slower. delaunaytri just hangs and i have to force quit matlab.i considered writing mex function but i havent got a clue how delaunayn works. i did a 'edit delaunayn' and noticed it uses qhullmx which cannot be edited.

are there any common speedy alternatives to the delaunayn functionality?

Subject: alternative to delaunayn

From: Bruno Luong

Date: 9 Oct, 2009 06:01:22

Message: 5 of 9

"Jveer " <jveer@jveer.com> wrote in message <ham34i$hm4$1@fred.mathworks.com>...

>
> this is how i use it : tetr=delaunayn(P',{'QJ'}) where P is a 3Xn matrix. n is usually very large.
>
> delaunay3 is slower. delaunaytri just hangs and i have to force quit matlab.i considered writing mex function but i havent got a clue how delaunayn works. i did a 'edit delaunayn' and noticed it uses qhullmx which cannot be edited.
>
> are there any common speedy alternatives to the delaunayn functionality?

Your description remains muddy. What is "very large n"? What is slow? Which Matlab version are you runing? Do you have repeat points (or almost?) in your data. In the latest releases, DELAUNAYN use a C or fortran library from "qhull" group, which is one of the most reliable with decent speed, and already compiled. So what *else* do you want to MEX? What make you believe you can do better than people who devote their life for this topic?

For N=10000 (10^4) uniform random points in R^3, it takes less than a second on my PC (2009B).

The theoretical worse complexity is O(N^2) in R^3. In practice, it's slightly more than O(N) as showed in the below code:

>> n=2.^(10:16);
t = zeros(size(n));
for k=1:length(n)
    P=rand(3,n(k));
    tic; tetr=delaunayn(P'); t(k)=toc;
end
t
P=polyfit(log(n),log(t),1);
fprintf('time = O^%g\n',P(1));
loglog(n,t);

t =

    0.0962 0.2053 0.4423 0.9752 2.0511 4.1500 8.5410

time = O^1.08233
>>

% Bruno

Subject: alternative to delaunayn

From: Bruno Luong

Date: 9 Oct, 2009 06:14:02

Message: 6 of 9

Sorry should be:

fprintf('time = O(n^%g)\n',P(1))

t =

    0.1027 0.2188 0.4458 0.9682 2.0011 4.0891 8.4991

time = O(n^1.06165)
>>

% Bruno

Subject: alternative to delaunayn

From: Rune Allnor

Date: 9 Oct, 2009 08:56:51

Message: 7 of 9

On 9 Okt, 03:20, "Jveer " <jv...@jveer.com> wrote:
> Rune Allnor <all...@tele.ntnu.no> wrote in message <b636c673-7327-4e75-8243-64ffe57f3...@f10g2000vbf.googlegroups.com>...
> > On 8 Okt, 23:16, "Jveer " <jv...@jveer.com> wrote:
> > > i meant * way too SLOW
>
> > Two comments:
>
> > 1) Higher-dimensional geometric algorithms *are* slow. Don't be
> >    surprised if the complexity goes something like O(f(N)^k)
> >    where k is the number of dimensions. With a bit of luck,
> >    f(N) < N, but don't rely on it.
> > 2) For non-specific number of dimensions, a lot os stuff that
> >    could have been optimized by a compiler, has to remain
> >    non-optimized. If you have a specific application in mind,
> >    write a special purpose application that is optimized
> >    for that problem.
>
> > Rune
>
> thanks for the reply Rune.
>
> this is how i use it : tetr=delaunayn(P',{'QJ'}) where P is a 3Xn matrix. n is usually very large.
>
> delaunay3 is slower. delaunaytri just hangs and i have to force quit matlab.i considered writing mex function but i havent got a clue how delaunayn works.  

Well, I'm currently writing a triangulator for 2D data.
Believe me, that's not something that is done in a hurry.

Just use what you have. Accept that computations take time.
Leave the computer to work in your free time; overnight,
through weekends, in vacations etc. No need for you to
babysit the computer while it does its thing.

Rune

Subject: alternative to delaunayn

From: Damian Sheehy

Date: 9 Oct, 2009 12:49:46

Message: 8 of 9

DelaunayTri is generally 3-4 times faster than DELAUNAY3/DELAUNAYN as they
use different underlying algorithms.
If your input data is highly degenerate, which I suspect yours is, the
performance is reduced as additional computation is performed to guarantee
robustness and the integrity of the output.
Examples of degenerate data include data in a grid, prismatic distribution
of points, points lying on the surface of a cylinder etc.
The performance of DelaunayTri when triangulating degenerate datasets was
improved in release R2009b.
This performance can further improved by shuffling the points prior to
insertion.
For example, given a set of points X, shuffle them as follows;
k = randperm(num_points)';
X = X(K,:);
dt = DelaunayTri(X);
For highly degenerate datasets the performance of DelaunayTri is no better
than DELAUNAY3/DELAUNAYN.
However, DelaunayTri is guaranteed to be robust and to provide a valid
triangulation output in the presence of degeneracies.
Based on my experience (~20 yrs) with Delaunay triangulations you will not
get much better performance than what you are seeing without compromising
robustness/integrity, and that's not practical in a commercial setting.

For dimensions higher than 3D you hit the "curse of dimensionality", as
others have pointed out, as size and complexity grows exponentially.
In general the practicality of Delaunay triangulations maxes out long before
you reach 10D.

If you would care to share particulars (data/requirements) about your
problem off-line I would be more than happy to provide advice; feel free to
contact me directly.


Best regards,


Damian

"Jveer " <jveer@jveer.com> wrote in message
news:ham34i$hm4$1@fred.mathworks.com...
> Rune Allnor <allnor@tele.ntnu.no> wrote in message
> <b636c673-7327-4e75-8243-64ffe57f3301@f10g2000vbf.googlegroups.com>...
>> On 8 Okt, 23:16, "Jveer " <jv...@jveer.com> wrote:
>> > i meant * way too SLOW
>>
>> Two comments:
>>
>> 1) Higher-dimensional geometric algorithms *are* slow. Don't be
>> surprised if the complexity goes something like O(f(N)^k)
>> where k is the number of dimensions. With a bit of luck,
>> f(N) < N, but don't rely on it.
>> 2) For non-specific number of dimensions, a lot os stuff that
>> could have been optimized by a compiler, has to remain
>> non-optimized. If you have a specific application in mind,
>> write a special purpose application that is optimized
>> for that problem.
>>
>> Rune
>
> thanks for the reply Rune.
>
> this is how i use it : tetr=delaunayn(P',{'QJ'}) where P is a 3Xn matrix.
> n is usually very large.
>
> delaunay3 is slower. delaunaytri just hangs and i have to force quit
> matlab.i considered writing mex function but i havent got a clue how
> delaunayn works. i did a 'edit delaunayn' and noticed it uses qhullmx
> which cannot be edited.
>
> are there any common speedy alternatives to the delaunayn functionality?

Subject: alternative to delaunayn

From: Luigi Giaccari

Date: 11 Oct, 2009 16:53:03

Message: 9 of 9

"Jveer " <jveer@jveer.com> wrote in message <halisn$s3s$1@fred.mathworks.com>...
> as most of you probably already know the in built 'delaunayn' function is way too also for realistic practical applications.
>
> does anyone know of any alternatives with the same functionality?
>
> how about creating a c mex version of it?

The data you sent me is structured, I told you delaunayn is a waste od time.

Use instead:

http://www.advancedmcode.org/structured-tedrahedral-mesh-generation.html

Regards

Luigi

http://www.advancedmcode.org

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