GLTree:Fast K-Nearest Neighbors Search

August 25, 2009 by Luigi Giaccari · 8 Comments
Filed under: Algorithms, Computational Geometry

Rating: +2 (from 2 votes)

Rating: 10.0/10 (5 votes cast)

In this file you can find a simple but very effective algorithm for Nearest Neighbour Search which I megalomaniacly called the GLTree.

You want more? go to the Professional version of GLTree

It has been designed for uniformly random data, where is the fastest I ever used, but works fine even on sparse ones. If points are too sparse, for example logspace data, search is still performed correctly but speed can degenerate to a brute search algorithm. In these cases a different data structure is needed but for lack of time I haven’t still coded. If query points are close to reference it is very efficient on sparse dataset too.

The tree can be build without running any search. The pointer passed to workspace can be used for the above routines. The tree costruction has linear time complexity and it is very fast, so it becomes advantageus against brute search even for a small number of points. I’d like to point that in GL-Tree searching has linear complexity (on uniform dataset) instead of n*log(n) like in kd-tree.
It is possible to choose if return the distances.

This release includes:

NNSearch

It only supports 2D points and 3D points.

It also possible to ask for personalized versions like:

different points data structure or class. To use the utility as C++ library.
Detections of sparse dataset. (sparse dataset are detected very soon so it is convenient to switch to a kd-tree data structure).
More efficient in terms of memory and speed costruction of the tree.
Personilzed functions, NNgraph, box search…
user’s suggestions
explanations on how the algorithm works

Some of this functions are brand new so please advise me if any error occurs.

Here is an example on 2D, find 1e6 neighbours in 1e6 reference:

N=1000000;
%random reference and query points
px=rand(N,1);%reference
py=rand(N,1);
qpx=rand(N,1);%query
qpy=rand(N,1);

tic
ptrtree=BuildGLTree2DFEX(px,py);
NNG=NNSearch2DFEX(px,py,qx,qy,ptrtree);
toc

Output:

1.46715 s

Downloads:

2D version Download Now
3D version Download Now
2D version precompiled Win32
3D version precompiled Win32

You want more? go to the Professional version of GLTree

Rating: 10.0/10 (5 votes cast)

Rating: +2 (from 2 votes)

Popularity: 7% [?]

Share and Enjoy:

8 Comments

Tags: 2d, 3D, GLTree, nearest neighbor

Fast Convex Hull Algorithm

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

Rating: 0 (from 0 votes)

Rating: 10.0/10 (2 votes 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 (2 votes cast)

Rating: 0 (from 0 votes)

Popularity: 28% [?]

Share and Enjoy:

8 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