Fast Convex Hull Algorithm

August 24, 2009 by Luigi Giaccari · 6 Comments
Filed under: Algorithms, Computational Geometry

Rating: 0 (from 0 votes)

Rating: 10.0/10 (1 vote cast)

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)

N=1000000;
x=rand(N,1);
y=rand(N,1);

tic
chull=ConvHull2D(x,y);%ConvHull2D
toc

tic
chull2=convhull(x,y); %Matlab built-in routine
toc

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:

giaccariluigi@msn.com

Download Now

Rating: 10.0/10 (1 vote cast)

Rating: 0 (from 0 votes)

Popularity: 34% [?]

Share and Enjoy:

6 Comments

Tags: 2d, Convex Hull

In Polygon Test For Convex Polygon

August 22, 2009 by Luigi Giaccari · Leave a Comment
Filed under: Computational Geometry, Geometry

Rating: 0 (from 0 votes)

Rating: 0.0/10 (0 votes cast)

This is Brand new so please advise-me if problems occurs.

Here you can find an m-file with three different algorithms for inpolygon test.
Depending on the input data, the one that is extimate to be the best will be chosen.

This version do not support the onpolygon output so tollerance is not necessary. Maybe in my next revision this feature will be added.

I’ll be very glad receiving suggestion (even on preferred sintax), questions bug reports.

SYNTAX:

in=InPolyConvex(qx,qy,x,y)

Input:

qx : The points to be tested, vector [Nx1] of x coordinate.
qy : The points to be tested, vector [Nx1] of y coordinate.
x : The x coordinate of vertices of the convex polygon [Nx1] The syntax assumes that the vertices are specified in consecutive order.
y : The y coordinate of vertices of the convex polygon [Nx1] The syntax assumes that the vertices are specified in consecutive order.

Output:

in : An Nx1 logical array with IN(i) = TRUE if P(i,:) lies within the region.

Notes:

InPolyConvex do not support on polygon options so tollerance is not necessary.
InPolyConvex do not support edges input format of the polygon.

Maybe in the next revision these two feature will be added.

EXAMPLE:

%query points
Nq=100;
qx=rand(Nq,1);
qy=rand(Nq,1);
%the convex polygon: a square
x=.2+[0,.5,.5,0]';
y=.3+[0,0,.5,.5]';
in=InPolyConvex(qx,qy,x,y);
figure;
hold on
axis equal
plot(x,y)
plot(qx(in),qy(in),'.r');
plot(qx(~in),qy(~in),'.k');
legend('Polygon','Inside','Outside')

For bugs,questions,suggestions just contact me at :

giaccariluigi@msn.com

Download Now

Rating: 0.0/10 (0 votes cast)

Rating: 0 (from 0 votes)

Popularity: 19% [?]

Share and Enjoy:

N-dimensional Convex Hull: Quicker Hull Algorithm

August 9, 2009 by Luigi Giaccari · 1 Comment
Filed under: Algorithms, Computational Geometry

Rating: +1 (from 1 vote)

Rating: 10.0/10 (1 vote cast)

Time comparison between quicjer and quick hull algorithm

Time comparison between quicker and quick hull algorithm

The Matlab convhulln is a gateway to the quickhull algorithm ( see www.qhull.org ). In my opinion, one weak point of this mex routine is that it processes all the points without performing any preliminary filtering.
In many cases it would be faster if only the point that can be part of the convhull were send to the quick hull algorithm.

Here is proposed an algorithm that can reduce the number of points before sending them to the mex routine.
For large models in dimensions lower than 6 the speed improvement can be even of several factors.

Unfortunately filtering points costs time and for high dimensions becomes unadvantageous.But no problem in these cases the algorithm just switch to the normal convhulln.

A test to compare performances is provided. Acknowledgments about bugs or incorrect timing are greatly appreciated.

For any problem, bug, information or suggestion just contact me at:

giaccariluigi@msn.com

Coming soon the how does it work section.