RE: [Algorithms] merging of points in 3D space

[Charles B. <cb...@cb...>]

There's code for this in Galaxy.

At 09:57 AM 4/18/2003 -0700, Jon Watte wrote:
>
>> 1.000 1.000 1.000
>> 0.999 1.001 1.000
>> 1.000 1.002 0.989 etc
>
>
>Either sort by one axis, and then walk the list, merging points 
>that are close enough (you only need to look a certain distance 
>ahead in the list to find matches). This is vaguely N*sqrt(N) in 
>run-time, assuming number of neighbors you need to consider 
>grows as root of total number of verts.
>
>Or round/quantize all points to even multiples of your weld 
>distance (typically, convert them all to shorts with the 
>appropriate scaling factor), and use a hash table to find 
>matches as you insert into the table. This is N run-time, in the 
>same sense as hashing is N in run-time.
>

-------------------------------------------------------
Charles Bloom    cb...@cb...    http://www.cbloom.com