find close points in a point cloud

find close points in a point cloud

Post by Gernot Fri » Fri, 19 Aug 2005 22:42:05


This is my code:

void RemoveClosePoints(double* xIso, double* yIso, int nIso, double
maxdist)
{
for(unsigned int i=0; i<nIso; ++i)
{
for(unsigned int j=i+1; j<nIso; ++j)
{
// if the points are closer than "maxdist"
if(abs(xIso[i]-xIso[j])<=maxdist && abs(yIso[i]-yIso[j])<=maxdist)
{
// make it inaccessable in the list
--nIso;
xIso[j] = xIso[nIso];
yIso[j] = yIso[nIso];
vIso[j] = vIso[nIso];
--i;
break;
}
}
}
}

how to make that faster?


--
-Gernot
int main(int argc, char** argv) {printf
("%silto%c%cf%cgl%ssic%ccom%c", "ma", 58, 'g', 64, "ba", 46, 10);}

________________________________________
Looking for a good game? Do it yourself!
GLBasic - you can do
www.GLBasic.com
 
 
 

find close points in a point cloud

Post by Stefan Ryb » Fri, 19 Aug 2005 22:50:50


To make it faster you have to avoid the check each point against each point by some
accelerating structur like a hash bucket list. Means put points in buckets addressed by a
hashvalue calculated from the point. This way you just need to test against all the points
in the bucket the point is and the buckets next to it.

Regards
Stefan

 
 
 

find close points in a point cloud

Post by Gernot Fri » Fri, 19 Aug 2005 23:29:11


"Stefan Rybacki" < XXXX@XXXXX.COM > schrieb im Newsbeitrag



Nice! Thx!
 
 
 

find close points in a point cloud

Post by Simon Plan » Sat, 20 Aug 2005 17:29:45


Or for 3d points store them in an octree or a kd-tree.

Simon
 
 
 

find close points in a point cloud

Post by Stefan Ryb » Sat, 20 Aug 2005 17:58:56


A kd-tree is suiteable for any dimension k ;)

Stefan
 
 
 

find close points in a point cloud

Post by Simon Plan » Sat, 20 Aug 2005 18:08:34


Of course. Weird that one usualy calls them three-dimensional kd-trees
instead of 3d-trees. :-)