5.0

5.0 | 2 ratings Rate this file 344 downloads (last 30 days) File Size: 7.61 KB File ID: #22260

Fast Convex Hull Algorithm

by Luigi Giaccari

 

27 Nov 2008 (Updated 09 Dec 2008)

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

I am interested in collaboration

Download Now | Watch this File

File Information
Description

Even if totally m-code, this routine is particulary fast in computing convex hull of 2D points. In many cases seems to be much faster than the matlab library routine. The reason is because differently from convhull, this algorithm jumps the call to unique function which can be very slow for large models .  
Algorithm is very simple, it's based on cross product.  
 
It is brand new, so please let me know if something goes wrong!  
 
ConvHull2D returns indices into the X and Y vectors of the points on the convex hull.  
 
Example: (convex hull of 1000000 random points)  
 
N=1000000;  
x=rand(N,1);  
y=rand(N,1);  
 
tic  
chull=ConvHull2D(x,y);  
toc  
 
   
tic  
chull2=convhull(x,y); %Matlab built-in routine  
toc  
 
Output:  
Elapsed time is 0.104134 seconds.  
Elapsed time is 1.207817 seconds.  
 
For any problem,bug, information or suggestion just contact me at:  
 
giaccariluigi@msn.com  

MATLAB release MATLAB 7.5 (R2007b)
Other requirements Should work on all platforms
Tags for This File  
Everyone's Tags
Tags I've Applied
Add New Tags Please login to tag files.
Comments and Ratings (5)
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.
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

Public Submission Policy

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 Disclaimer prior to use.

Contact us at files@mathworks.com