Re: Fast search for a number within tolernaces


"Jonas Forssell" <jonasforssell@xxxxxxxx> wrote in message
news:538f1709.0506062158.3fd75bdc@xxxxxxxxxxxxxxxxxxxxx
> Gentlemen,
>
> I have a set of three dimensional nodes - each with a position in
> space (x,y,z).
> I need to write a fast algorithm in Java to merge nodes that are close
> - i.e. within a specific tolerance.
>
> Easy way: Run through the array of nodes, check each node against
> every other node and merge if needed. This will take an awful amount
> of time when the array is 500.000 nodes or larger.
>
> Smart way:?
>
> Thanks for your help

How do you do a merge? If you set the x,y,z values of the merged node
to be the average of the input nodes, you now have to go back and check
nodes that you have already passed because your new merged node might
be close enough to one of them as to trigger an additional merge.


.