FAST CONVEX HULL ALGORITHM

Totally m-code routine to compute convex hull in 2D space faster than the Matlab native convhull.

Description

You can find the description at:

http://www.advancedmcode.org/fast-convex-hull-algorithm.html

Acknowledgements

The author wishes to acknowledge the following in the creation of this submission:
N-DIMENSIONAL CONVEX HULL: QUICKER HULL ALGORITHM
This submission has inspired the following:
N-DIMENSIONAL CONVEX HULL: QUICKER HULL ALGORITHM

• MATLAB release: MATLAB 7.6 (R2008a)
• Other requirements: Should work on all platforms
• Other Files: ConvHull2D300209/ConvHull2D.m, ; ConvHull2D300209/HowDoesItWork.m, ; ConvHull2D300209/SpeedTestConvHull2D.m, ; license.txt

[Thomas Clark]

For any more than 20 points, this is drastically slower than convhull - order of magnitude slower for 10^7 points. If the elapsed times reported by the author are correct, then there is something SERIOUSLY wrong with his computer.

Although well commented, the code is barely vectorised (all computation within for and while loops).

Luigi, in response to one of your comments - preallocating vectors can actually decrease your instantaneous memory use - it only wastes memory if you preallocate too large a chunk of memory.

Here's the code to prove the relative performance of this against convhull:

%% PUT THIS IN A SCRIPT AND RUN IT
profile on
profile clear
Npoints = logspace(1,6,15);
lengthN = numel(Npoints);
convhull_times = zeros(lengthN,1);
chull2d_times = zeros(lengthN,1);
for i = 1:lengthN
    N=ceil(Npoints(i));
    x=rand(N,1);
    y=rand(N,1);
    tic
    chull1 = convhull(x,y);
    convhull_times(i) = toc;
    tic
    chull=ConvHull2D(x,y);
    chull2d_times(i) = toc;
end
    
figure()
semilogx(Npoints,convhull_times,'g-')
hold on
semilogx(Npoints,chull2d_times,'b-')
legend({'Native convhull';'convhull2d'})
title('Performance comparison')
profile viewer

[Luigi Giaccari]

That'is it Ifound
Mister clark there is nothing wrong in my pc, maybe you should
turn the profile off when you run a new test try this. Especially
before giving low and inappropriate rating.

%% PUT THIS IN A SCRIPT AND RUN IT
% profile on
% profile clear

%%%%%%%%%%%%%%%%%%%%%%%%

%Maybe you forgot this !!!!

profile off

profile off

profile off

profile off

%%%%%%%%%%%%%%%%%%%%%%%

Npoints = logspace(1,6,15);
lengthN = numel(Npoints);
convhull_times = zeros(lengthN,1);
chull2d_times = zeros(lengthN,1);
for i = 1:lengthN
    N=ceil(Npoints(i));
    x=rand(N,1);
    y=rand(N,1);
    tic
    chull1 = convhull(x,y);
    convhull_times(i) = toc;
    tic
    chull=ConvHull2D(x,y);
    chull2d_times(i) = toc;
end
     
figure()
semilogx(Npoints,convhull_times,'g-')
hold on
semilogx(Npoints,chull2d_times,'b-')
legend({'Native convhull';'convhull2d'})
title('Performance comparison')
% profile viewer

[Thomas Clark]

**** CORRECTION TO MY PREVIOUS COMMENT ****

Luigi has correctly pointed out that my use of the profiler disadvantages his algorithm as opposed to convhull.

Re-running the test, I find that actually, yes, there is a significant speed advantage over convhull across the entire range tested (up to 10^7 points).

Luigi and I are corresponding in order to vectorise the code to reduce bottlenecks. This is likely to be fixed imminently, giving an order of magnitude increase in speed over most of the range, with respect to convhull.

Thanks Luigi for a great idea; and sorry to jump to the wrong conclusion to start with.

[Derek O'Connor]

Using an 8-core 2x Intel(R) Xeon(R) CPU E5345 @ 2.33GHz with Matlab R2008a on Windows Vista 64, Thomas Clark's test gave these results :

    Matlab ConvHull2D
    0.0016 0.0003
    0.0007 0.0007
    0.0008 0.0009
    0.0008 0.0011
    0.0009 0.0025
    0.0011 0.0040
    0.0014 0.0089
    0.0029 0.0155
    0.0048 0.0325
    0.0109 0.0644
    0.0274 0.1530
    0.0648 0.3265
    0.1875 0.7368
    0.5172 1.5775
    1.1987 3.6044

ConvHull2D seems to be 3 times slower than Matlab's convhull.

Derek O'Connor

[Luigi Giaccari]

From your timing I suspect you did the same error of Tomas Clark

You should turn the profile off, profile only works on m-code, the native convhull is a mex routine, so it only slow down my algorithm.

To be sure please send a report about the way rou ran your test. If there is any problem I'll try to fix it.

[Andreas Bonelli]