Fast Convex Hull Algorithm

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

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:  
 
[e-mail]  

• MATLAB release: MATLAB 7.5 (R2007b)
• Other requirements: Should work on all platforms

[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.