5.0

5.0 | 3 ratings Rate this file 68 downloads (last 30 days) File Size: 7.41 KB File ID: #22260

FAST CONVEX HULL ALGORITHM

by Luigi Giaccari

 

27 Nov 2008 (Updated 24 Aug 2009)

Code covered by the BSD License  

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

Download Now | Watch this File

File Information
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
Zip File Content  
Other Files ConvHull2D300209/ConvHull2D.m,
ConvHull2D300209/HowDoesItWork.m,
ConvHull2D300209/SpeedTestConvHull2D.m,
license.txt
Tags for This File  
Everyone's Tags
Tags I've Applied
Add New Tags Please login to tag files.
Comments and Ratings (6)
02 Dec 2008 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

02 Dec 2008 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

03 Dec 2008 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.

21 Dec 2008 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

23 Dec 2008 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.

19 May 2009 Andreas Bonelli  
Please login to add a comment or rating.
Updates
01 Dec 2008

cleared the code and fixed a little bug

02 Dec 2008

grammars errors

04 Dec 2008

Fixed a bug on colinear points

06 Dec 2008

Improved treatment for colinear points

09 Dec 2008

Another small bug fixed Thanks to liu-daohai report

12 Jan 2009

Added speedtest and graphical explanation of the algorithm

12 Jan 2009

added acknoledgemets

13 Jan 2009

updated presentation, yesterday I missed it

18 Mar 2009

changed the presentation

04 May 2009

Fixed a little bug

20 Jul 2009

Changed title

24 Aug 2009

Added link

Tag Activity for this File
Tag Applied By Date/Time
2d Cristina McIntire 01 Dec 2008 14:07:51
mathematics Luigi Giaccari 01 Dec 2008 14:08:07
aerospace Luigi Giaccari 01 Dec 2008 14:08:07
automotive Luigi Giaccari 01 Dec 2008 14:08:07
mesh Luigi Giaccari 01 Dec 2008 14:08:07
convex Luigi Giaccari 01 Dec 2008 14:08:07
hull Luigi Giaccari 01 Dec 2008 14:08:07
fast Luigi Giaccari 01 Dec 2008 14:08:07
polygon Luigi Giaccari 01 Dec 2008 14:08:07
qhull Luigi Giaccari 01 Dec 2008 14:08:07
triangulation Luigi Giaccari 01 Dec 2008 14:08:07
delaunay Luigi Giaccari 01 Dec 2008 14:08:07
points Luigi Giaccari 02 Dec 2008 14:49:21
geometry Luigi Giaccari 02 Dec 2008 14:49:21
image processing Luigi Giaccari 13 Jan 2009 15:55:10
simulation Luigi Giaccari 13 Jan 2009 15:55:10
 

MATLAB Central Terms of Use

NOTICE: Any content you submit to MATLAB Central, including personal information, is not subject to the protections which may be afforded information collected under other sections of The MathWorks, Inc. Web site. You are entirely responsible for all content that you upload, post, e-mail, transmit or otherwise make available via MATLAB Central. The MathWorks does not control the content posted by visitors to MATLAB Central and, does not guarantee the accuracy, integrity, or quality of such content. Under no circumstances will The MathWorks be liable in any way for any content not authored by The MathWorks, or any loss or damage of any kind incurred as a result of the use of any content posted, e-mailed, transmitted or otherwise made available via MATLAB Central. Read the complete Terms prior to use.

Contact us at files@mathworks.com