Fast Convex Hull Algorithm
Even if totally m-coded, this routine is particularly fast in computing convex hull of 2D points. In many cases seems to be much faster than the matlab library routine. The main reason is that, 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!
Since I received comments about different timings this version includes a speed test to compare ConvHull2D to the native matlab convhull. There is also a graphical explanation on how the algorithm works.
ConvHull2D returns indices into the X and Y vectors of the points on the convex hull.
Example: (convex hull of 1000000 random points)
Output:
Elapsed time is 0.104134 seconds.(ConvHull2D)
Elapsed time is 1.207817 seconds.(Matlab built in)
For any problem, bug, information or suggestion just contact me at:
Download Now
Popularity: 33% [?]
Related Posts
Comments
6 Comments on Fast Convex Hull Algorithm
-
r0l0kcs on
Fri, 18th Sep 2009 23:28
-
Taywin on
Fri, 25th Sep 2009 21:03
-
JackM on
Tue, 15th Dec 2009 19:51
This looks like Graham Scan to me.
May I ask: Do you have any sources on incremental convex hull algorithms “for dummies” like me? That would be great. 
Or is Graham Scan the same as incremental convex hull?
[Reply]
I’m trying again… Last time it submitted an empty text…
Have you every tried to compare for the case when all points are vertices of convex hull as well? I mean all 1 million points are actually vertices of a convex hull. Because your algorithm speed seems to rely heavily filtering. If there is a case that your filtering does not benefit the speed at all, I just want to know whether the built-in function is still slower than yours or how much faster it is compared to yours. Of course, this is an extreme case, but I just want to see how it goes. Thank you.
[Reply]
Luigi Giaccari Reply:
September 26th, 2009 at 13:10
My routine is faster if all points are already part of the convex hull.
Run the following test:
N=1000000; teta=linspace(0,2*pi,N); x=cos(teta); y=sin(teta); tic chull1=ConvHull2D(x,y); fprintf('ConvHull2D took : %4.4f s\n', toc); tic chull2=convhull(x,y); fprintf('Matlab Routine: %4.4f s\n', toc);
it leads to:
ConvHull2D took : 0.6692 s
Matlab Routine: 5.5856 s
The built-in uses the quick hull algorithm this point cofiguration is patological.
My routine suffers logspace data where generally the convhull is formed by only a few points. On this data the filtering step erases no points. Anywa it should be faster in this case too, since ConvHull2D doesn’t call the unique fucntion which is the main bottlenech for the Matlab convhull.
We also have to consider that Convhull2D, apart from the sort function, is totally m-coded, no precompiled files. Convhull instead is a MEX routine.
If you need more infos just ask.
Luigi
[Reply]
Yes, this is nothing new but just a variation of Graham’s scan (FYI, you don’t need to calculate angles in Graham’s scan). If you are looking for fast convex hull methods, there is for example a paper “Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions” by Timothy Chan, which explains a method which run in O(n*log(h)) time.
[Reply]
Luigi Giaccari Reply:
December 15th, 2009 at 20:55
Oh you seem pretty expert! 
can you please send me the paper, I would like to give it a look!
Thanks
[Reply]
Tell me what you're thinking...
and oh, if you want a pic to show with your comment, go get a gravatar!
Include MATLAB code in your comment by doing the following:
<pre lang="MATLAB">
%insert code here
</pre>
Translator
By N2H Follow Us
Video Posts
-
Luigi Giaccari Reply:
September 18th, 2009 at 23:35
Umh,
You should really study
In Graham scan there is a sorting operation based on the angle others points forms with the first one. Here sort is performed on y (or x ) coordinate, plus there is a filtering preprocessor step.
I actually thing this algorithm is not something new since it seems just too easy. Anyway it works, it is very fast.
Please report comments on http://www.advancedmcode.org/
I don’t usually go on Youtube.
Last question, no I don’t have no code about incremental convex hull, this one was coded for fun, I don’t work in the convex hull field…..Sorry
For any more question just ask,
Bye
Luigi
[Reply]