Find clusters in 3D point data using a massively parallel algorithm -
i have large number of points in 3d space (x,y,z) represented array of 3 float structs. have access strong graphics card cuda capability. want following:
divide points in array clusters every point within cluster has maximum euclidean distance of x @ least 1 other point within cluster.
examle in 2d: 
the "brute force" way of doing of course calculate distance between every point , every other point, see if of distances below threshold x, , if mark points belonging same cluster. o(n²) algorithm.
this can done in parallel in cuda ofcourse n² threads, there better way?
the algorithm can reduced o(n) using binning:
- impose 3d grid spaced x, 3d lattice (each cell of lattice cubic bin);
- assign each points in space corresponding bin (the bin geometrically contains points);
- every time need evaluate distances 1 point, use points in bin of point , ones in 26 neighbouring bins (3x3x3 = 27)
the points in other bins further x, don't need evaluate distances @ all.
in way, assuming constant density in points, have compute distance constant number of pair points / total number of points.
assigning points bins o(n) well.
if points not uniformly distributed, bins can smaller (and must consider more 26 neighbours evaluate distances) , sparse.
this typical trick used molecular dynamics, ray tracing, meshing,... know of term binning molecular dynamics simulation: name can change (link-cell, kd-trees use same principle, if more articulated), algorithm remains same!
and, news, algorithm suited parallel implementation.
refs:
Comments
Post a Comment