K-Nearest Neigbors and Radius (Range) Search

August 7, 2009 by Luigi Giaccari · 2 Comments
Filed under: Algorithms, Computational Geometry, Mathematics

Rating: +1 (from 1 vote)

Rating: 0.0/10 (0 votes cast)

BruteSearchMex

When the dataset is small, when you have to run only a few number of search, or when the dimensions of points is large, the brute search method is still faster than kd-trees data structure. Computing the distances one by one take a minor time than building the tree.
Some of this problems have became less gravous since the introduction of GLTree (file id 22190) which allows for a very fast tree construction.
Despite this, very small dataset are still terrain for brute search algorithms.

I saw many k-neighbours utilities on FEX, but all them were m-coded. I think such a brute calculation is not an m-code job. So I developed my own Nearest Neighbour finder. It is nothing special it just computes all the distances and take the ones required from the input parameters, but of course the mex implementation make it even faster than vectorized m-code.

The following utilities are provided:

Nearest neighbor
K-Nearest neighbors
Radius Search

They al supports N-dimensions and work on double, it is possible to choose if return the distances.

Here is a time comparison with a vectrized m-code:

N=1000000;%number of reference points
Nq=100;%number of query points
dim=3;%dimension of points
k=3;%number of neighbor

tic
[idc,dist]=BruteSearchMex(p',qp','k',k);%MEX
toc

tic
[idc,dist]=knnsearch(qp,p,k);% VECTORIZED M-CODE
toc

p=rand(N,dim);
qp=rand(Nq,dim);

Output:

Elapsed time is 0.962640 seconds.
Elapsed time is 18.813100 seconds.

For info, questions, suggestions, bugs: giaccariluigi@msn.com

Download Now

Rating: 0.0/10 (0 votes cast)

Rating: +1 (from 1 vote)

Popularity: 42% [?]

Share and Enjoy:

2 Comments

Tags: 2d, 3D, Image processing, knn, nD, nearest neighbor, search

BuildSphere, get a sphere surface model

August 6, 2009 by Luigi Giaccari · 2 Comments
Filed under: Geometry, Graphics

Rating: 0 (from 0 votes)

Rating: 8.0/10 (1 vote cast)

This can be considered the triangular version of file exchange id 20888 which uses quad patches.

BUILDSPHERE:
Returns the triangulated model of a sphere using the icosaedron subdivision method.

INPUT:

n (integer number) indicates the number of subdivisions, it can assumes values between 0-inf. The greater n the better will look the surface but the more time will be spent in surface costruction and more triangles will be put in the output model.

OUTPUT:

In p (n x 3) and t(m x 3) we can find points and triangles indexes of the model. The sphere is supposed to be of unit radius and centered in (0,0,0). To obtain spheres centered in different location, or with different radius, is just necessary a translation and a scaling transformation. These operation are not performed by this code because it is extremely convenient, in order of time performances, to do them out of the function avoiding to call the costruction step each time.

NOTE:

This function is more efficient than the matlab command sphere in terms of dimension of the model/ accuracy of recostruction. This due to well triangulated model that requires a minor number of patches for the same geometrical recostruction accuracy. Possible improvement are possible in time execution and model subdivision flexibility.

EXAMPLE: